Курсовая (1). Программная реализация и анализ алгоритмов поиска в тексте

• Название: Программная реализация и анализ алгоритмов поиска в тексте
• Дата: 09.11.2020
• Размер: 1.83 Mb.
• Имя файла: Курсовая (1).docx
• Тип: Курсовая; #149201
• страница: 4 из 5

1.2.3 Алгоритм Бойера и Мура

Алгоритм Бойера и Мура считается наиболее быстрым среди алгоритмов, предназначенных для поиска подстроки в строке. Он был разработан Р. Бойером и Д. Муром в 1977 году. Преимущество этого алгоритма в том, что необходимо сделать некоторые предварительные вычисления над подстрокой, чтобы сравнение подстроки с исходной строкой осуществлять не во всех позициях – часть проверок пропускаются как заведомо не дающие результата.

Существует множество вариаций алгоритма Бойера и Мура, рассмотрим простейший из них, который состоит из следующих шагов. Первоначально строится таблица смещений для искомой подстроки. Далее идет совмещение начала строки и подстроки и начинается проверка с последнего символа подстроки. Если последний символ подстроки и соответствующий ему при наложении символ строки не совпадают, подстрока сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа подстроки. Если же символы совпадают, производится сравнение предпоследнего символа подстроки и т.д. Если все символы подстроки совпали с наложенными символами строки, значит, найдена подстрока и поиск окончен. Если же какой-то (не последний) символ подстроки не совпадает с соответствующим символом строки, далее производим сдвиг подстроки на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомой подстроки, либо не будет достигнут конец строки (рис. 3). На рисунке символы, подвергшиеся сравнению, выделены жирным шрифтом.

Величина сдвига в случае несовпадения последнего символа вычисляется, исходя из следующего: сдвиг подстроки должен быть минимальным, таким, чтобы не пропустить вхождение подстроки в строке. Если данный символ строки встречается в подстроке, то смещаем подстроку таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в подстроке. Если же подстрока вообще не содержит этого символа, то сдвигаем подстроку на величину, равную ее длине, так что первый символ подстроки накладывается на следующий за проверявшимся символом строки.

Величина смещения для каждого символа подстроки зависит только от порядка символов в подстроке, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа подстроки.

i

i

i

Строка

A

B

C

A

F

D

F

A

B

C

A

B

D

Подстрока

A

B

C

A

B

D A

B

C A

A B

B C

D A

B

D

Рис.3. Демонстрация алгоритма Бойера и Мура [8]

//описание функции алгоритма Бойера и Мура

int BMSearch(char *string, char *substring){

int sl, ssl;

int res = -1;

sl = strlen(string);

ssl = strlen(substring);

if ( sl == 0 )

cout << "Неверно задана строка\n";

else if ( ssl == 0 )

cout << "Неверно задана подстрока\n";

else {

int i, Pos;

int BMT[256];

for ( i = 0; i < 256; i ++ )

BMT[i] = ssl;

for ( i = ssl-1; i >= 0; i-- )

if ( BMT[(short)(substring[i])] == ssl )

BMT[(short)(substring[i])] = ssl - i - 1;

Pos = ssl - 1;

while ( Pos < sl )

if ( substring[ssl - 1] != string[Pos] )

Pos = Pos + BMT[(short)(string[Pos])];

else

for ( i = ssl - 2; i >= 0; i-- ){

if ( substring[i] != string[Pos - ssl + i + 1] ) {

Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;

break;

}

else

if ( i == 0 )

return Pos - ssl + 1;

cout << "\t" << i << endl;

}

}

return res;

}

Алгоритм Бойера и Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск. Таким образом, данный алгоритм является наиболее эффективным в обычных ситуациях, а его быстродействие повышается при увеличении подстроки или алфавита. В наихудшем случае трудоемкость рассматриваемого алгоритма .

Существуют попытки совместить присущую алгоритму Кнута, Морриса и Пратта эффективность в «плохих» случаях и скорость алгоритма Бойера и Мура в «хороших» – например, турбо-алгоритм, обратный алгоритм Колусси и другие.

Каждый алгоритм поиска позволяет эффективно действовать лишь для своего класса задач, об этом еще говорят различные узконаправленные улучшения. Алгоритм поиска подстроки в строке следует выбирать только после точной постановки задачи, которые должна выполнять программа. [1]

ГЛАВА 2. РАЗРАБОТКА ПРИЛОЖЕНИЯ ДЛЯ ПОИСКА В ТЕКСТЕ

2.1 Описание среды разработки

JavaScript это язык, который позволяет Вам применять сложные вещи на web странице — каждый раз, когда на web странице происходит что-то большее, чем просто её статичное отображение — отображение периодически обновляемого контента, или интерактивных карт, или анимация 2D/3D графики, или прокрутка видео в проигрывателе, и т.д. — можете быть уверены, что скорее всего, не обошлось без JavaScript. Это третий слой слоёного пирога стандартных web технологий, два из которых (HTML и CSS) мы детально раскрыли в других частях учебного пособия.

• 
  HTML - это язык разметки, который мы используем для визуального и смыслового структурирования нашего web контента, например, определяем параграфы, заголовки, таблицы данных, или вставляем изображения и видео на страницу.
  
• 
  CSS - это язык стилей с помощью которого мы придаем стиль отображения нашего HTML контента, например придаем цвет фону (background) и шрифту, придаем контенту многоколоночный вид.
  
• 
  JavaScript язык программирования, который позволяет Вам создать динамически обновляемый контент, управляет мультимедиа, анимирует изображения, впрочем, делает всё, что угодно. Окей, не все, что угодно, но все равно, это удивительно, что можно достичь с помощью нескольких строк JavaScript кода. [3]
  

Почему JavaScript? Единственная и весомая причина – идеальное сочетание с HTML, следовательно, получившуюся программу мы сможем опробовать в обычном браузере, и при этом не скачивать стороннее программное обеспечение

2.2 Постановка задачи

Пусть задана строка, состоящая из некоторого количества символов. Проверим, входит ли заданная подстрока в данную строку. Если входит, то найдем номер, начиная с какого символа строки, то есть, определим первое вхождение заданной подстроки в исходной строке. [1]

2.3 Структура приложения

Описание работы программы:



1) Необходимо ввести искомый фрагмент

2) Прикрепить текстовый файл, в котором будет искаться фрагмент ( Кодировка – UTF-8 )

3) Нажать кнопку найти

4) Программа ищет фрагмент в тексте, если фрагмент присутствует, то программа выводит текст на экран, выдает с какого символа начинается, в каком месте находится, а так же показывает количество совпадений и трудоемкость

5) При необходимости все результаты можно вывести в отдельный файл

Как это должно выглядеть:



Если искомого фрагмента нет, программа выведет что «Фрагмент отсутствует»



Приложение__2_-_Реализация_функции_вывода'>Приложение_1-_Реализация_ввода'>2.4 Код приложения

Приложение 1- Реализация ввода

let reader = new FileReader();

reader.onload = function(event) {

 let contents = event.target.result;

 console.log("Содержимоефайла: " + contents);

 document.getElementById("fileinner").innerHTML = contents;

};

reader.onerror = function(event) {

 console.error("Файлнеможетбытьпрочитан! код " + event.target.error.code);

};

let control = document.getElementById("filein");

control.addEventListener("change", function(event) {

 // Когда происходит изменение элементов управления, значит появились новые файлы

 let i = 0,

  files = control.files,

  len = files.length;

 for (; i < len; i++) {

  console.log("Filename: " + files[i].name);

  console.log("Type: " + files[i].type);

  console.log("Size: " + files[i].size + " bytes");

 }

 let input = event.target;

 reader.readAsText(input.files[0]);

}, false);

Приложение 2 - Реализация функции вывода

function writeFile(name, value)

{

 var val = value;

 let frag = "Искомый фрагмент: ";

 frag += document.getElementById("Frag1").innerHTML;

 frag += ".\n\n"; 

 letSR = "Прямой поиск подстроки в строке:\n";

 

 let postxt = "Позиция: ";

 postxt += delbr(document.getElementById("Pos=1").innerHTML);

 postxt += "\n";

 let sovptxt = "Совпадений: ";

 sovptxt += document.getElementById("Sovp1").innerHTML;

 sovptxt += ".\n";

 let timetxt = "Трудоёмкость: ";

 timetxt += document.getElementById("Time1").innerHTML;

 timetxt += ".\n";

 SR += postxt;

 SR += sovptxt;

 SR += timetxt;

 SR += "\n\n";

 . . . 

 let sme = document.getElementById("sme").innerHTML;

 if (document.getElementById("Pos=1").innerHTML == "")

 {

  val = "Тестовые данные отсутствуют.";

 }

 var download = document.createElement("a");

 download.href = "data:text/plain;content-disposition=attachment;filename=file," + val + frag + SR + SR2 + SR3 + sme;

 download.download = name;

 download.style.display = "none";

 download.id = "download"; document.body.appendChild(download);

 document.getElementById("download").click();

 document.body.removeChild(download);

}

Приложение 3 – Реализация прямого поиска

function DirectSearch(string1,substring1)

{

 let und = "undefined";

 let stringarr = string1;

 let substringarr = substring1;

 let sl = stringarr.length;

 let ssl = substringarr.length;

 let res = -1;

 let arr = [];

 if (sl == 0)

 {

  console.log("Невернозаданастрока\n");

  return und;

 }

 else

 {

  if ( ssl == 0 )

  {

   console.log("Неверно задана подстрока\n");

   return und;

  }

  else

  {

   for (let i = 0; i < sl - ssl + 1; i++)

   {

    for (let j = 0; j < ssl; j++)

    {

     if ( substringarr[j] != stringarr[i+j] )

     {

      break;

     }

     else if (j == ssl - 1)

     {

      res = i;

      arr.push(res);

      break;

     }

    }

   }

   return arr;

  }

 }

}

Приложение 4 –Реализация алгоритма Кнута-Морриса-Пратта

function KMPSearch(string1,substring1)

{

 let und = "undefined";

 let stringarr = string1;

 let substringarr = substring1;

 let sl = stringarr.length; 

 let ssl = substringarr.length;

 let res = -1;

 let arr = [];

 if (sl == 0)

 {

  console.log("Невернозаданастрока\n");

  return und;

 }

 else

 {

  if ( ssl == 0 )

  {

   console.log("Неверно задана подстрока\n");

   return und;

  }

  else

  {

   let i = 0, j = 0, k = -1;

   let d = [-1];

   while ( j < ssl - 1 )

   {

    while(k >= 0 && substringarr[j] != substringarr[k])

    { 

     k = d[k];

    }

    j++;

    k++;

    if (substringarr[j] == substringarr[k])

    {

     d[j] = d[k];

    }

    else

    {

     d[j] = k;

    }

   }

   i = 0;

   j = 0;

   while ( j < ssl && i < sl)

   {

    while ( j >= 0 && stringarr[i] != substringarr[j])

    {

     j = d[j];

    }

    i++;

    j++;

    if (j==ssl)

    {

     res = i -ssl;

     arr.push(res);

     j = 0;

     i += 1 - ssl;

    }

   }

   if (j != ssl)

   {

    res = -1;

   }

  }

  returnarr;

 }

}