В настоящее врея компьютеры содержат огромное количество данных. Однако извлечение текстовой информации затрудняется когда написано с ошибками или когда неточно известно.
Эта статья посвящена алгоритмам приблизительного сравнения строк текста. Она даёт упрощенное но ясное описание алгоритмов с примерами.
Во-первых, мы собираемся объяснить процедуры конструирующиефонетические коды для искомого текста, который звучит одинаково, но пишется по-разному. Во-вторых, мы объясним процедуры дающие разные типы метрика похожести текста, используемые в поиске позволяющем ошибки. В заключении, алгоритмы сравниваются, чтобы читатель смог выбрать наиболее подходящий. Смотрите также ресурсыв конце статьи.
Обсуждаемые здесь процедуры используются для облегчения поиска в базах данных, когда известно, как текст проиносится, но не как пишется. Для этого конструируются фонетические коды для искомого текста, в то время как база данных предварительно индексируется используя эти коды. Фамилии, которые звучит одинаково, но пишутся по-разному, как SMITH и SMYTH, имеют одинаковый код и могут помещаться рядом. Использование фонетических кодов уменьшает проблемы поиска из-за неправильного или разного написания.
Фонетическое кодирование очень полезно для объединения перечней личных имён или имён предприятий. Оно также используется для опознавания речи и в поисковыых системах баз данных таких как анти-террористических.
Саундэкс (Soundex) конструирует фонетические коды для личных имён. Результирующий код состоит из одной буквы и трёх цифр, каждая из которых соответствует 6 согласным звукам. Алгоритм впервые был применён в переписи США в 1880 году.
В 1985 году новый алгоритм Саундэкс Дэйча-Мокотоффа (Daitch-Mokotoff Soundex) было применён для фонетического кодирования фамилий славянских и идиш с похожим произношением но разным написанием. Наиболее важные улучшения по сравнению с Саундэкс: более длинный код - 6 символов; производятся два разных кода когда возможны два разных произношения; кодирование использует 10 цифр от 0 к 9.
Система идентификации и сведений штата Нью-Йорк (NYSIIS - New York State Identification and Intelligence System) была разработана в 1970 году посредством строгого эпирического анализа. В этом алгоритме конструируется фонетический код до 6 букв.
Алгоритм Метафон (Metaphone) фонетически кодирует слова путем уменьшения их до 16 согласных звуков: B, X, S, K, J, T, F, H, L, M, N, P, R, 0, W, Y. Ноль представляет звук "th"; X представляет "sh".
Двойной метафон (Double metaphone) - улучшенный вариант Метафона. Этот алгоритм фонетически кодирует слова путем уменьшения их до 12 согласных звуков. Оно возвращает два кода если слово имеет два возможных произношения.
Другие процедуры, обсуждаемые здесь, используют различные типы метрики текстуального сходства. Их можно использовать в поиске, позволяющем ошибки.
Многие из этих процедур вычисляют сходство двух строк как число между 0 и 1. Величина 0 означает, что строки полностью различны. Величина 1 означает совершенное совпадение строк. Промежуточные значения соответствуют частичному совпадению.
Алгоритмы метрик похожести полезны для проверки орфографии, для опознавания речи, для анализа ДНК, для обнаружения плагиата, для нахождения разницы между файлами и для дистанционного обновления дисплея.
Для двух строк одинаковой длины, дистанция Хэмминга (Hamming distance) - количество мест, в которых строки имеют разные символы.
Дистанция редактирования (edit distance) между двумя строками определяется как минимальное число вставок, замен и удалений символов необходых для того, чтобы преобразовать первую строку во вторую. Дистанция 0 означает, что строки идентичны.
Алгоритм был изобретён в 1965 советским научным работником Владимиром Левенштейном. По этой причине Дистанция редактирования называется также Дистанцией Левенштейна.
Имеются современные варианты алгоритма, придавая различные веса вставке, замене и удалению.
Триграммное сходство (trigram similarity) между двумя строками определяется числом совпадающих символьных триплетов в обоих строках. Алгоритм можно обобщить на n-граммы, где n=1, 2, ...
Строки string1 и string2 пополняются слева и справа одним символом пробела. Затем строки разделяются на триплеты (триграммы). Окончательно, сходство вычисляется по формуле:
s = 2*m / (a + b).
Здесь:
m - число совпадающих триграмм
a - число триграмм в string1
b - число триграмм в string2
Алгоритм Ратклиффа/Обершелпа (Ratcliff/Obershelp pattern recognition) вычисляет сходство двух строк как удвоенное число соответствующих символов разделённое на полное число символов в строках. Соответствующие символы находятся в самой длинной общей подпоследовательности плюс, рекурсивно, соответствующие символы в остальной части по любую сторону от самой длинной общей подпоследовательности.
Сходство Джаро-Винклера (Jaro-Winkler similarity) было применено в переписи США и использовано в последующей обработке.
Для данных строк string1 и string2, их сходство задаётся формулой:
s = m/3a + m/3b + (m-t)/3m.
Здесь:
m - число соответствующих символов
a - длина string1
b - длина string2
t - число перестановок
Два символа считаются соответствующими, только если они находятся не дальше чем (max(a,b)/2 - 1). Первый соответствующий символ в string1 сравнивается с первым соответствующим символом в string2; второй соответствующий символ в string1 сравнивается со вторым соответствующим символом в string2, и так далее. Число соответствующих символов делённое на 2 даёт число перестановок.
Улучшенный метод Джаро-Винклера использует веса отличные от 1/3. Он также даёт меньший вес некоторым типам ошибок: визуального сканирования, клавишного ввода и в конце строки.
Имеются некоторые алгоритмы, учитывающие ошибки ввода на клавиатуре: V вместо B, 6 вместо Y и так далее.
Смотрите также обширную библиографию Интернета на английском языке.