Приблизительное сравнение строк

Реализация на C#:

public static int LevenshteinDistance(string string1, string string2)

{

int diff;

int [,] m = new int [string1.Length+1,string2.Length+1];

for (int i=0;i<=string1.Length;i++) m[i,0]=i;

for (int j=0;j<=string2.Length;j++) m[0,j]=j;

for (int i=1;i<=string1.Length;i++)

for (int j=1;j<=string2.Length;j++)

{

diff=(string1[i-1]==string2[j-1])?0:1;

m[i,j]=Math.Min(Math.Min(m[i-1,j]+1,

m[i,j-1]+1),

m[i-1,j-1]+diff);

}

return m[string1.Length,string2.Length];

}

Причины, по которым сравнение образца и подстроки текста оказалось неудачным, принято разбивать на классы. Отличие может состоять в том, что соответствующие символы образца и подстроки оказались различными, что в образце есть символы, отсутствующие в тексте, что в тексте есть символы, отсутствующие в образце. Ошибки набора, как правило, относятся к одной из этих трех категорий, причем ошибка, заключающаяся в перестановке двух соседних букв интерпретируется как два отличия первого типа.
Мы будем искать соответствие подстроке с точностью k, где через k обозначено максимальное число отличий, упомянутых в предыдущем образце. Нам придется учесть несколько возможностей. Что означает, например, несовпадение первого символа строки-образца и текста? Оно может означать, как несовпадение символов, так и отсутствие нужного символа в строке или тексте. Даже если символы совпадают, может оказаться, что лучшее совпадение строк в целом достигается, если считать первый символ образца или текста пропущенным.
Попробуем, например, сравнить строку ad со строкой read. При сравнении с начала текста мы получаем два возможных 2-приближенных совпадения (либо символ a следует заменить на r, а символ d - на e, либо нужно добавить к образцу пропущенные впереди символы re). Кроме того при сравнении с первой позиции есть 3-приближенное совпадение (добавить символ r и заменить ad на ea). При сравнении со второй позиции имеется 2-приближенное совпадение (заменить ad на ea), а также 1-приближенное совпадение (добавить впереди символ e).
Видно, что число возможностей очень велико. Даже при совпадении нескольких первых символов, за которым следует несовпадение, может оказаться, что лучшее приближение достигается при изменении некоторых символов в образце или в тексте или добавлении тех или иных символов туда и сюда. Как найти все возможности, сохранив при этом разумную структуру данных и алгоритма? Сложность алгоритма, проверяющего все возможности, чересчур высока. Мы предпочитаем упростить алгоритм за счет усложнения структур данных.
Будем решать задачу путем создания матрицы с именем diffs, в которой накапливается вся до сих пор полученная информация. Каждому символу образца соответствует строка матрицы, а каждому символу текста - столбец. Значения элементов матрицы показывают, насколько похожи текст и образец к данному моменту. Скажем, если на пересечении пятой строки и 27-го столбца стоит число 4, то это означает, что при сравнении первых пяти символов образца с отрезком текста, кончающимися 27-ым символом, мы обнаружили четыре расхождения.
Число расхождений в произвольной позиции определяется тремя соседними элементами матрицы, находящимися непосредственно сверху, слева и сверху-слева от данного. При использовании верхнего соседа мы предполагаем, что в тексте пропущен элемент образца. При использовании левого соседа предполагается, что в образце пропущена буква из текста. Сосед по диагонали отвечает за совпадение или несовпадение символов. Точнее говоря, клетку diffs[i, j] мы заполняем минимумом из трех значений:

1. diffs[i - 1, j - 1], если substring[i] = text[j], в противном случае diffs[i - 1, j - 1] + 1;

2. diffs[i - 1, j] + 1 (символ substring[j] отсутствует в тексте);

3. diffs[i, j - 1] + 1 (символ substring[j] отсутствует в образце).

При запуске процесса мы обращаемся к строке i = 0, лежащей вне матрицы, и полагаем значения ее элементов равными нулю, а также к лежащему вне матрицы столбцу j = 0, и полагаем значения его элементов равными номеру соответствующей строки. Пример заполнения для образца their и текста hello there friends приведен в таблице.

Таблица. Матрица diffs для образца their и текста hello there friends

h

e

l

l

o

t

h

e

r

e

f

r

i

e

n

d

s

t

h

e

i

r

При реализации этой процедуры мы должны были бы задать не только образец и текст, но и переменную для хранения минимального числа различий. Алгоритм заполнял бы матрицу столбец за столбцом, пока нижний элемент столбца не превышает установленной границы. Это означает, что алгоритм не обязан хранить в памяти все ST элементов матрицы (где S - длина образца, а T - длина текста), а может обойтись 2S ячейками для хранения целых чисел: достаточно хранить вычисляемый столбец и предыдущий, которым он однозначно определяется.
Такой тип алгоритмов относится к "динамическому программированию".

Анализ:

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

Ссылки:

· Реализация на c#

Дата добавления: 2015-07-17