Примерное соответствие строк

Нечеткий поиск в Mediawiki по запросу «злой смайлик» дает в качестве предполагаемого результата «андре эмоции».

В информатике , приблизительное сопоставление строк (часто называемое в просторечии поиском нечетких строк ) — это метод поиска строк соответствуют шаблону которые приблизительно (а не точно) . Проблема приблизительного сопоставления строк обычно делится на две подзадачи: поиск приблизительных совпадений подстроки внутри заданной строки и поиск словарных строк, которые приблизительно соответствуют шаблону.

Обзор

Близость совпадения измеряется количеством примитивных операций, необходимых для преобразования строки в точное совпадение. Это число называется расстоянием редактирования между строкой и шаблоном. Обычные примитивные операции:

• вставка: кроватка → co a t
• удаление: co a t → кроватка
• замена: co a t → co s t

Эти три операции можно обобщить как формы замены, добавив символ NULL (здесь обозначенный *) везде, где символ был удален или вставлен:

• вставка: co * t → co a t
• удаление: co a t → co * t
• замена: co a t → co s t

Некоторые средства приблизительного сопоставления также рассматривают транспозицию , при которой позиции двух букв в строке меняются местами, как примитивную операцию.

• : стоимость котировки → ​ транспонирование

Различные приблизительные сопоставители накладывают разные ограничения. Некоторые средства сопоставления используют одну глобальную невзвешенную стоимость, то есть общее количество примитивных операций, необходимых для преобразования совпадения в шаблон. Например, если шаблон — катушка , фольга отличается одной заменой, катушки — одной вставкой, масло — одним удалением, а жеребенок — двумя заменами. Если все операции считаются за одну единицу стоимости и предел установлен в единицу, фольга , катушки и масло будут считаться спичками, а жеребенок — нет.

Другие сопоставители указывают количество операций каждого типа отдельно, а третьи устанавливают общую стоимость, но позволяют присваивать разным операциям разные веса. Некоторые средства сопоставления допускают отдельное присвоение пределов и весов отдельным группам в шаблоне.

Постановка задачи и алгоритмы

Одно из возможных определений проблемы приблизительного сопоставления строк следующее: Учитывая строку-шаблон $P=p_{1}p_{2}...p_{m}$ и текстовая строка $T=t_{1}t_{2}\dots t_{n}$, найти подстроку $T_{j',j}=t_{j'}\dots t_{j}$ в T , которая из всех подстрок T имеет наименьшее расстояние редактирования до шаблона P .

При грубом подходе можно было бы вычислить расстояние редактирования до P для всех подстрок T, а затем выбрать подстроку с минимальным расстоянием. Однако этот алгоритм будет иметь время работы O ( n ³  м ).

Лучшее решение, предложенное Селлерсом, опирается на динамическое программирование . Он использует альтернативную формулировку задачи: для каждой позиции j в тексте T и каждой позиции i в шаблоне P вычисляется минимальное расстояние редактирования между i первыми символами шаблона, $P_{i}$и любая подстрока $T_{j',j}$ T , который заканчивается в позиции j .

Для каждой позиции j в тексте T и каждой позиции i в шаблоне P просмотрите все подстроки T, заканчивающиеся на позиции j , и определите, какая из них имеет минимальное значение.отредактируйте расстояние до первых шаблона P. символов Запишите это минимальное расстояние как E ( i , j ). Вычислив E ( i , j ) для всех i и j , мы можем легко найти решение исходной проблемы: это подстрока, для которой E ( m , j ) минимальна ( m — длина шаблона P ).

Вычисление E ( m , j ) очень похоже на вычисление расстояния редактирования между двумя строками. Фактически, мы можем использовать алгоритм дистанционных вычислений Левенштейна для E ( m , j ), с той лишь разницей, что мы должны инициализировать первую строку нулями и сохранить путь вычисления, то есть использовали ли мы E ( i − 1, j ), E( i , j - 1) или E ( i - 1, j - 1) при вычислении E ( i , j ).

Затем в массиве, содержащем значения E ( x , y ), мы выбираем минимальное значение в последней строке, пусть это будет E ( x ₂ , y ₂ ), и следуем по пути вычислений назад, обратно к строке номер 0. Если поле, к которому мы пришли, было E (0, y ₁ ), то T [ y ₁ + 1] ... T [ y ₂ ] является подстрокой T с минимальным расстоянием редактирования до шаблона P .

Вычисление массива E ( x , y ) занимает время O ( mn ) с помощью алгоритма динамического программирования, а фаза обратной работы занимает время O ( n + m ).

Еще одна недавняя идея — соединение по подобию. Когда сопоставление базы данных относится к большому объему данных, время O ( mn ) с алгоритмом динамического программирования не может работать в течение ограниченного времени. Итак, идея состоит в том, чтобы уменьшить количество пар-кандидатов вместо вычисления сходства всех пар строк. Широко используемые алгоритмы основаны на проверке фильтров, хешировании, локально-зависимом хешировании (LSH), попытках и других жадных и аппроксимирующих алгоритмах. Большинство из них спроектированы так, чтобы соответствовать какой-либо платформе (например, Map-Reduce) для параллельных вычислений.

Онлайн и офлайн

Традиционно алгоритмы приблизительного сопоставления строк подразделяются на две категории: онлайновые и офлайновые. С помощью онлайн-алгоритмов шаблон можно обработать перед поиском, а текст — нет. Другими словами, онлайн-методы выполняют поиск без индекса. Ранние алгоритмы онлайн-приблизительного сопоставления были предложены Вагнером и Фишером. и Селлерс. Оба алгоритма основаны на динамическом программировании , но решают разные задачи. Алгоритм Селлерса приблизительно ищет подстроку в тексте, тогда как алгоритм Вагнера и Фишера вычисляет расстояние Левенштейна , подходящее только для нечеткого поиска по словарю.

Методики онлайн-поиска неоднократно совершенствовались. Пожалуй, самый Известным усовершенствованием является битовый алгоритм (также известный как алгоритм сдвига-или и сдвига-и), который очень эффективен для относительно коротких строк шаблонов. Алгоритм Bitap — это сердце Unix поиска утилиты agrep . Обзор алгоритмов онлайн-поиска был сделан Дж. Наварро.

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

Приложения

Общие применения приблизительного соответствия включают проверку орфографии . Благодаря наличию большого количества данных о ДНК сопоставление нуклеотидных последовательностей стало важным применением. Приблизительное соответствие также используется при фильтрации спама . Связывание записей — это распространенное приложение, в котором сопоставляются записи из двух разных баз данных.

Сопоставление строк нельзя использовать для большинства двоичных данных, таких как изображения и музыка. Они требуют разных алгоритмов, например, акустического снятия отпечатков пальцев .

Распространенный инструмент командной строки fzf часто используется для интеграции приблизительного поиска строк в различные приложения командной строки.

См. также

• Поиск концепции
• Расстояние Яро – Винклера
• Расстояние Левенштейна
• Хэширование с учетом местоположения
• Метафон
• Алгоритм Нидлмана – Вунша
• Обнаружение плагиата
• Регулярные выражения для нечеткого и нечеткого сопоставления
• Алгоритм Смита – Уотермана
• Саундекс
• Строковая метрика
• База данных векторов для поиска семантического сходства

Ссылки

Цитируемые работы

• Баеза-Йейтс, Р.; Наварро, Г. (1998). «Быстрое приблизительное сопоставление строк в словаре» (PDF) . Учеб. ШПАЙР'98 . IEEE CS Пресс. стр. 14–22.
• Бойцов, Леонид (2011). «Методы индексирования для приблизительного словарного поиска: Сравнительный анализ». Журнал экспериментальной алгоритмики . 16 (1): 1–91. дои : 10.1145/1963190.1963191 . S2CID   15635688 .
• Кормен, Томас ; Лейзерсон, Ривест (2001). Введение в алгоритмы (2-е изд.). С Прессой. стр. 364–7. ISBN  978-0-262-03293-3 .
• Гасфилд, Дэн (1997). Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  978-0-521-58519-4 .
• Наварро, Гонсало (2001). «Экскурсия по приблизительному сопоставлению строк». Обзоры вычислительной техники ACM . 33 (1): 31–88. CiteSeerX   10.1.1.96.7225 . дои : 10.1145/375360.375365 . S2CID   207551224 .
• Наварро, Гонсало; Баеза-Йейтс, Рикардо; Сутинен, Эркки; Тархио, Йорма (2001). «Методы индексирования для приблизительного сопоставления строк» ​​(PDF) . Бюллетень инженерии данных IEEE . 24 (4): 19–27.
• Селлерс, Питер Х. (1980). «Теория и расчет эволюционных расстояний: распознавание образов». Журнал алгоритмов . 1 (4): 359–73. дои : 10.1016/0196-6774(80)90016-4 .
• ^ Скиена, Стив (1998). Руководство по разработке алгоритмов (1-е изд.). Спрингер. ISBN  978-0-387-94860-7 .
• Вагнер, Р.; Фишер, М. (1974). «Проблема построчной коррекции» . Журнал АКМ . 21 : 168–73. дои : 10.1145/321796.321811 . S2CID   13381535 .
• Зобель, Джастин; Дарт, Филип (1995). «Нахождение приблизительных совпадений в больших словарях». Программное обеспечение: практика и опыт . 25 (3): 331–345. CiteSeerX   10.1.1.14.3856 . дои : 10.1002/спе.4380250307 . S2CID   6776819 .

Дальнейшее чтение

• Баеза-Йейтс, Р.; Наварро, Г. (июнь 1996 г.). «Более быстрый алгоритм приблизительного сопоставления строк». В Дэне Хирксберге; Джин Майерс (ред.). Комбинаторное сопоставление с образцом (CPM'96), LNCS 1075 . Ирвин, Калифорния. стр. 1–23. CiteSeerX   10.1.1.42.1593 .
• Галил, Цви; Апостолико, Альберто (1997). Алгоритмы сопоставления с образцом . Оксфорд [Оксфордшир]: Издательство Оксфордского университета. ISBN  978-0-19-511367-9 .
• Майерс, Г. (май 1999 г.). «Быстрый бит-векторный алгоритм для приблизительного сопоставления строк на основе динамического программирования» (PDF) . Журнал АКМ . 46 (3): 395–415. дои : 10.1145/316542.316550 . S2CID   1158099 .
• Укконен, Э. (1985). «Алгоритмы приблизительного сопоставления строк» . Информация и контроль . 64 (1–3): 100–18. дои : 10.1016/S0019-9958(85)80046-2 .

Внешние ссылки

• Проект Фламинго
• Проект эффективной обработки запросов на сходство с последними достижениями в области приблизительного сопоставления строк на основе порогового значения расстояния редактирования.
• StringMetric проект библиотеки Scala строковых метрик и фонетических алгоритмов.
• Natural project — библиотека обработки естественного языка JavaScript , которая включает реализации популярных строковых метрик.