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

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

     Причины, по которым сравнение образца и подстроки текста оказалось неудачным, принято разбивать на классы. Отличие может состоять в том, что соответствующие символы образца и подстроки оказались различными, что в образце есть символы, отсутствующие в тексте, что в тексте есть символы, отсутствующие в образце. Ошибки набора, как правило, относятся к одной из этих трех категорий, причем ошибка, заключающаяся в перестановке двух соседних букв интерпретируется как два отличия первого типа.
     Мы будем искать соответствие подстроке с точностью 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] мы заполняем минимумом из трех значений:

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

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

Таблица. Матрица diffs для образца trim и текста try the trumpet

		t	r	y		t	h	e		t	r	u	m	p	e	t
	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
t	1	0	1	1	1	0	1	1	1	0	1	1	1	1	1	0
r	2	1	0	1	2	1	1	2	2	1	0	1	2	2	2	1
i	3	2	1	1	2	2	2	2	3	2	1	1	2	3	3	2
m	4	3	2	2	2	3	3	3	3	3	2	2	1	2	3	3

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

Сайт управляется системой uCoz