Приближенные алгоритмы сопоставления строк
https://stackoverflow.com/questions/49263
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Здесь, на работе, нам часто нужно найти строку из списка строк, которая наиболее близко соответствует какой-либо другой входной строке.В настоящее время мы используем алгоритм Нидлмана-Вунша.Алгоритм часто возвращает много ложноположительных результатов (если мы устанавливаем слишком низкий минимальный балл), иногда он не находит совпадение, когда должен (когда минимальный балл слишком высок), и в большинстве случаев нам нужно проверять результаты вручную.Мы подумали, что нам следует попробовать другие альтернативы.
Есть ли у вас какой-либо опыт работы с этими алгоритмами?Знаете ли вы, как эти алгоритмы сравниваются друг с другом?
Я был бы очень признателен за ваш совет.
PS:Мы пишем на C #, но вас это не должно волновать - я спрашиваю об алгоритмах в целом.
О, простите, я забыла упомянуть об этом.
Нет, мы не используем его для сопоставления дублирующихся данных.У нас есть список строк, которые мы ищем - мы называем его search-list.И затем нам нужно обработать тексты из различных источников (таких как RSS-каналы, веб-сайты, форумы и т.д.) - Мы извлекаем части этих текстов (для этого есть целые наборы правил, но это не имеет значения) и нам нужно сопоставить их со списком поиска.Если строка совпадает с одной из строк в списке поиска - нам нужно выполнить некоторую дальнейшую обработку объекта (что также не имеет значения).
Мы не можем выполнить обычное сравнение, потому что строки, извлеченные из внешних источников, в большинстве случаев содержат некоторые дополнительные слова и т.д.
Во всяком случае, это не для обнаружения дубликатов.
Решение
Итак, Needleman-Wunsch (NW) - классический сквозной ("глобальный") выравниватель из литературы по биоинформатике.Он уже давно был доступен как "align" и "align0" в пакете FASTA.Разница заключалась в том, что версия "0" не была столь предвзятой в отношении избежания разрыва в концах, что часто позволяло легче проводить высококачественные внутренние совпадения.Смит-Уотерман, я подозреваю, что вы в курсе, является местным элайнером и является первоначальной основой BLAST.У FASTA также был собственный локальный элайнер, который немного отличался.Все это, по сути, эвристические методы оценки расстояния Левенштейна, относящиеся к метрике подсчета очков для отдельных пар символов (в биоинформатике, часто задаются Dayhoff / "PAM", Henikoff & Henikoff или другими матрицами и обычно заменяются чем-то более простым и разумно отражающим замены в лингвистической морфологии слов применительно к естественному языку).
Давайте не будем придавать большого значения ярлыкам:Расстояние Левенштейна, как указано, по крайней мере, на практике, в основном является расстоянием редактирования, и вы должны оценить его, потому что его невозможно вычислить в целом, и точное вычисление обходится дорого даже в интересных особых случаях:вода там быстро становится глубокой, и поэтому у нас есть эвристические методы, давно пользующиеся хорошей репутацией.
Теперь что касается вашей собственной проблемы:несколько лет назад мне нужно было проверить точность коротких считываний ДНК с эталонной последовательностью, которая, как известно, верна, и я придумал то, что назвал "привязанные выравнивания".
Идея состоит в том, чтобы взять ваш набор ссылочных строк и "переварить" его, найдя все местоположения, где встречается данная N-символьная подстрока.Выберите N, чтобы таблица, которую вы создаете, была не слишком большой, но также и чтобы подстроки длиной N не были слишком распространенными.Для небольших алфавитов, таких как базы ДНК, можно создать идеальный хэш для строк из N символов, составить таблицу и объединить совпадения в связанный список из каждой ячейки.Записи списка должны идентифицировать последовательность и начальную позицию подстроки, которая соответствует ячейке, в списке которой они встречаются.Это "якоря" в списке строк для поиска, по которым, вероятно, будет полезно выравнивание по NW.
При обработке строки запроса вы берете N символов, начинающихся с некоторого смещения K в строке запроса, хэшируете их, просматриваете их ячейку, и если список для этой ячейки непустой, то вы просматриваете все записи списка и выполняете выравнивание между строкой запроса и строкой поиска, на которую ссылается запись.При выполнении этих выравниваний вы выравниваете строку запроса и строку поиска в привязку и извлекают подстроку строки поиска, которая имеет ту же длину, что и строка запроса, и которая содержит эту привязку с тем же смещением, K.
Если вы выберете достаточно длинную привязку длиной N и разумный набор значений смещения K (они могут быть распределены по строке запроса или ограничены низкими смещениями), вы должны получить подмножество возможных выравниваний и часто будете получать более четкие выигрыши.Обычно вам захочется использовать выравниватель NW с меньшим смещением по концу, подобный align0.
Этот метод пытается немного увеличить NW, ограничивая его ввод, и это приводит к увеличению производительности, потому что вы выполняете меньше выравниваний и они чаще выполняются между похожими последовательностями.Еще одна полезная вещь, которую можно сделать с вашим выравнивателем NW, - разрешить ему отключаться после возникновения некоторого количества или длины зазоров, чтобы сократить расходы, особенно если вы знаете, что не увидите совпадений среднего качества или не заинтересуетесь ими.
Наконец, этот метод использовался в системе с маленькими алфавитами, с K, ограниченным первыми 100 или около того позициями в строке запроса, и со строками поиска, намного большими, чем запросы (считывание ДНК составляло около 1000 оснований, а строки поиска были порядка 10000, поэтому я искал приблизительные совпадения подстрок, оправданные оценкой расстояния редактирования, в частности).Адаптация этой методологии к естественному языку потребует некоторого тщательного обдумывания:вы теряете в размере алфавита, но выигрываете, если строки вашего запроса и строки поиска имеют одинаковую длину.
В любом случае, одновременное использование нескольких привязок с разных концов строки запроса может оказаться полезным при дальнейшей фильтрации данных, передаваемых в NW.Если вы сделаете это, будьте готовы к возможной отправке перекрывающихся строк, каждая из которых содержит один из двух якорей, в выравниватель, а затем к согласованию выравниваний...или, возможно, дополнительно измените NW, чтобы подчеркнуть сохранение ваших якорей в основном неповрежденными во время выравнивания, используя штрафную модификацию во время выполнения алгоритма.
Надеюсь, это полезно или, по крайней мере, интересно.
Другие советы
Связано с расстоянием Левенштейна:возможно, вы захотите нормализовать его, разделив результат на длину более длинной строки, чтобы вы всегда получали число от 0 до 1 и чтобы вы могли осмысленно сравнивать расстояние пары строк (например, выражение L (A, B) > L (A, C) бессмысленно, если вы не нормализуете расстояние).
Альтернативными алгоритмами, на которые следует обратить внимание, являются агреп (Статья в Википедии об agrep), БЫСТРО и ВЗРЫВНО алгоритмы сопоставления биологических последовательностей.Это особые случаи приблизительное соответствие строк, также в Репозиторий алгоритмов Stony Brook.Если вы можете указать, чем строки отличаются друг от друга, вы, вероятно, могли бы сосредоточиться на специально разработанном алгоритме.Например, aspell использует некоторый вариант расстояния "soundslike" (soundex-metaphone) в сочетании с расстоянием "keyboard", чтобы приспособиться как к плохим правописателям, так и к плохим наборщикам.
Мы используем Расстояние Левенштейна метод проверки наличия дубликатов клиентов в нашей базе данных.Это работает довольно хорошо.
Использование FM - индекс с обратным отслеживанием, подобным тому, что в Галстук-бабочка выравниватель нечеткости
Чтобы свести к минимуму несоответствия из-за небольших вариаций или ошибок в правописании, я использовал алгоритм Metaphone, затем расстояние Левенштейна (масштабированное до 0-100 в процентах совпадения) в кодировках Metaphone для измерения близости.Похоже, это сработало довольно хорошо.
Чтобы подробнее остановиться на ответе Cd-MaN, похоже, вы столкнулись с проблемой нормализации.Не очевидно, как обрабатывать оценки между трассами разной длины.
Учитывая то, что вас интересует, вы можете захотеть получить p-значения для вашего выравнивания.Если вы используете Needleman-Wunsch, вы можете получить эти p-значения, используя статистику Карлина-Альтшула http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
BLAST сможет выполнить локальные выравнивания и оценить их, используя эти статистические данные.Если вас беспокоит скорость, это был бы хороший инструмент для использования.
Другой вариант - использовать HMMER.HMMER использует профильные скрытые марковские модели для выравнивания последовательностей.Лично я считаю, что это более эффективный подход, поскольку он также предоставляет информацию о местоположении. http://hmmer.janelia.org/
Раньше я работал с самыми грязными данными, которые вы когда-либо найдете.В среднем требовалось сопоставить около 5000 строк данных (что эквивалентно сотням тысяч долларов), что было совершенно изматывающим занятием.Моим первым опытом работы с нечетким сопоставлением был алгоритм из Mr Excel, написанный на VBA.У этого были определенные проблемы с последовательностью в том смысле, что то, что я ожидал от нуля процентов, таковым не являлось, а то, что составляло около 60 процентов, выглядело скорее как 90 процентов.Итак, я переехал в Левенштейн, а затем в Дамерау-Левенштейн.Это было значительное улучшение, но довольно медленное в Excel.Затем я перешел к Яро-Винклеру, но вскоре быстро отбросил его.Наконец, в 2016 году я написал свой собственный (на основе n-gram) и совершенствовал его в течение следующих 2 лет.Сегодня это дополнение под названием Flookup;вы можете получить его в Google Таблицах и посмотреть, как он работает.
