Cтрока x длины |x| = m записывается как x1x2 ... xm, где xi представляет i-й символ x. Подстрока xixi+1 ... xj строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная подстрока обозначается так xR(i,j). Обычно x будет обозначать искомый образец, а y - текстовую строку; |x| = m, |y| = n и, конечно, m<=n. Пример: x = trismegistus |x| = 12 x(7,10) = gist xR(7,4) = gems Обобщенная задача сопоставления строк, включающая в себя нахождение подстрок строки текста, близких к заданному образцу строки, называется также задачей нечеткого сопоставления строк. Задачу нечеткого сопоставления строк можно сформулировать следующим образом: Пусть даны образец x, |x| = m, и текст y, |y| = n, m, n > 0 и m < n. Пусть даны также целое k > 0 и функция расстояния d. Требуется найти все подстроки s текста y такие, что d(x, s) < k. Здесь и далее, d - метрика. Расстояние Хемминга [Hamming, 1982] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Это эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом. Если допускается сравнение строк разной длины, то, как правило, требуются также вставка и удаление. Если придать им тот же вес, что и замене, минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном [Levenstein, 1965]. Другая метрика равна минимальной цене преобразования в случае, когда разрешены только вставка и удаление. Это эквивалентно назначению цены 1 удалению и вставке, и 2 замене, так как последнюю можно заменить парой вставка-удаление. Первую из этих метрик мы ниже называем расстоянием Левенштейна, а вторую - расстоянием редактирования. Задача, таким образом, состоит в том, чтобы при заданной функции расстояния найти все подстроки текста, отстоящие от образца не более, чем на k. Если d является расстоянием Хемминга, задача называется сопоставлением строк с k несовпадениями, если же d - расстояние Левенштейна, задача называется сопоставлением строк с k различиями (или, иногда, ошибками). Наивный подход к задаче сопоставления строк, требующий времени O(mn), легко адаптировать к задаче k несовпадений, разрешив k несовпадений при сравнениях символов подстроки в тексте. Однако, как и для задачи сопоставления строк, для задач k несовпадений и k различий были изобретены более эффективные подходы. k несовпадений - Ландау-Вишкин k-различий - Ландау-Вишкин Их алгоритм гораздо лучше, если k пропорционально O(m/log n). Для неограниченных алфавитов он алгоритм быстрее, если k пропорционально O(log1/2m). Он, безусловно, превосходен, когда границей k является O(log1/2m). Заметим, однако, что при больших k, то есть когда k равняется O(m), его эффективность не лучше, чем у адаптации прямого, с квадратичным временем, подхода динамического программирования. SpeedSIP значительно снижает расходы на телефонную связь и сервисы: бесплатные звонки внутри сети, выгодные международные и междугородные звонки, СМС по всему миру, покупка прямого номер любой страны, видеосвязь и видеоконференции. В этом разделе : 8  k несовпадений - алгоритм Ландау-Вишкина В алгоритме k несовпадений Ландау-Вишкина строка текста анализируется с помощью 2-мерной таблицы несовпадений образца (pattern mismatch) pm[1:m-1, 1:2k+1], генерируемой на стадии предварительной обработки образца. 8  k-различий - алгоритм Ландау-Вишкина Алгоритм k различий Ландау-Вишкина основан на подходе, близком методу динамического программирования для вычисления расстояния между строками, который предложил Укконен.

8  k несовпадений - алгоритм Ландау-Вишкина 8  k-различий - алгоритм Ландау-Вишкина