Приближенные алгоритмы сопоставления строк
Здесь, на работе, нам часто нужно найти строку из списка строк, которая наиболее близко соответствует какой-либо другой входной строке. В настоящее время мы используем алгоритм Нидлмана-Вунша. Алгоритм часто возвращает много ложных срабатываний (если мы установили минимальный балл слишком низким), иногда он не находит соответствия, когда должен (когда минимальный балл слишком высок), и, в большинстве случаев, нам нужно проверить результаты вручную. Мы думали, что должны попробовать другие альтернативы.
Есть ли у вас опыт работы с алгоритмами? Знаете ли вы, как алгоритмы сравниваются друг с другом?
Буду очень признателен за совет.
PS: мы кодируем на C#, но вам не стоит об этом беспокоиться - я спрашиваю об алгоритмах в целом.
О, прости, я забыл упомянуть об этом.
Нет, мы не используем его для сопоставления дубликатов данных. У нас есть список строк, которые мы ищем - мы называем это search-list. И затем нам нужно обрабатывать тексты из разных источников (например, RSS-каналы, веб-сайты, форумы и т. Д.) - мы извлекаем части этих текстов (для этого есть целые наборы правил, но это не имеет значения), и нам нужно соответствовать те, кто против поиска списка. Если строка совпадает с одной из строк в списке поиска - нам нужно выполнить дальнейшую обработку вещи (что также не имеет значения).
Мы не можем выполнить нормальное сравнение, потому что строки, извлеченные из внешних источников, в большинстве случаев содержат некоторые дополнительные слова и т. Д.
Во всяком случае, это не для обнаружения дубликатов.
7 ответов
ОК, Needleman-Wunsch(NW) - классический комплексный ("глобальный") выравниватель из литературы по биоинформатике. Это было давно доступно как "align" и "align0" в пакете FASTA. Разница заключалась в том, что версия "0" не была настолько предвзятой для того, чтобы избежать пробела в конце, что часто позволяло предпочтить высококачественные внутренние совпадения. Смит-Уотерман, я подозреваю, что вы знаете, является местным специалистом и является оригинальной основой BLAST. У FASTA был свой собственный локальный выравниватель, который немного отличался. Все это по существу эвристические методы для оценки расстояния Левенштейна, относящегося к метрике оценки для отдельных пар символов (в биоинформатике, часто предоставляемых Dayhoff/"PAM", Henikoff&Henikoff или другими матрицами и обычно заменяемых чем-то более простым и более разумно отражающим замены в морфологии лингвистического слова применительно к естественному языку).
Давайте не будем в восторге от меток: расстояние Левенштейна, на которое ссылаются, по крайней мере, на практике, по сути, является расстоянием редактирования, и вы должны его оценивать, потому что его вообще невозможно вычислить, а точно вычислить дорого даже в особых особых случаях: вода быстро углубляется, и, таким образом, у нас есть эвристические методы длинной и хорошей репутации.
Теперь о вашей собственной проблеме: несколько лет назад мне пришлось проверять точность коротких чтений ДНК по отношению к эталонной последовательности, которая, как известно, была правильной, и я придумал то, что я назвал "привязанными привязками".
Идея состоит в том, чтобы взять набор ссылок и "переварить" его, найдя все места, где встречается данная N-символьная подстрока. Выберите N, чтобы создаваемая таблица была не слишком большой, но и чтобы подстроки длины N были не слишком распространены. Для небольших алфавитов, таких как основы ДНК, можно придумать идеальный хэш для строк из N символов, составить таблицу и объединить в цепочке совпадения из каждого списка. Записи списка должны идентифицировать последовательность и начальную позицию подстроки, которая отображается в корзину, в список которой они входят. Это "якоря" в списке искомых строк, в которых выравнивание NW может оказаться полезным.
При обработке строки запроса вы берете N символов, начинающихся с некоторого смещения K в строке запроса, хэшируете их, ищите их корзину, и если список для этой корзины не пуст, вы просматриваете все записи списка и выполняете выравнивания между строка запроса и строка поиска, указанная в записи. При выполнении этих выравниваний вы выстраиваете строку запроса и строку поиска на якоре и извлекаете подстроку строки поиска, которая имеет ту же длину, что и строка запроса, и которая содержит этот якорь с тем же смещением, K.
Если вы выберете достаточно большую длину привязки N и разумный набор значений смещения K (они могут быть распределены по строке запроса или ограничены низкими смещениями), вы должны получить подмножество возможных выравниваний и часто будете получать более четкие победители. Как правило, вы захотите использовать выравнивающий NW выравниватель с меньшим смещением.
Этот метод пытается немного увеличить NW, ограничивая его ввод, и это дает выигрыш в производительности, потому что вы делаете меньше выравниваний, и они чаще между похожими последовательностями. Еще одна хорошая вещь, которую нужно сделать с вашим NW-выравнивателем, - дать ему возможность сдаться после того, как произойдет некоторый или длительный разрыв, чтобы сократить расходы, особенно если вы знаете, что не собираетесь видеть или заинтересованы в матчах среднего качества.
Наконец, этот метод использовался в системе с маленькими алфавитами, где K ограничивался первыми 100 или около того позициями в строке запроса, а поисковые строки были намного больше, чем запросы (чтения ДНК составляли около 1000 базисов, а поисковые строки были включены порядка 10000, поэтому я искал приблизительные совпадения подстрок, специально рассчитанные для оценки расстояния редактирования). Адаптация этой методологии к естественному языку потребует тщательного осмысления: вы теряете размер алфавита, но выигрываете, если строки запроса и строки поиска имеют одинаковую длину.
В любом случае, одновременное использование нескольких якорей с разных концов строки запроса может быть полезным для дальнейшей фильтрации данных, передаваемых в NW. Если вы сделаете это, будьте готовы послать перекрывающие строки, каждая из которых содержит один из двух якорей, в выравниватель, а затем согласовать выравнивания... или, возможно, дополнительно изменить NW, чтобы подчеркнуть сохранение целостности ваших якорей во время выравнивания, используя модификацию штрафа во время выполнение алгоритма.
Надеюсь, что это полезно или хотя бы интересно.
Относительно расстояния Левенштейна: вы можете захотеть нормализовать его, разделив результат на длину более длинной строки, чтобы вы всегда получали число от 0 до 1 и чтобы вы могли сравнить расстояние между двумя строками в значимом значении. путь (выражение L(A, B) > L(A, C) - например - бессмысленно, если вы не нормализуете расстояние).
Альтернативные алгоритмы, на которые следует обратить внимание, - это agrep ( википедия по agrep), алгоритмы сопоставления биологических последовательностей FASTA и BLAST. Это особые случаи приближенного совпадения строк, также в хранилище алгоритма Stony Brook. Если вы можете указать, как строки отличаются друг от друга, вы можете сосредоточиться на специализированном алгоритме. Например, aspell использует некоторый вариант расстояния "звукоподобный" (soundex-metaphone) в сочетании с расстоянием "клавиатура" для размещения как плохих, так и плохих пишущих символов.
Мы используем дистанционный метод Левенштейна для проверки дубликатов клиентов в нашей базе данных. Это работает довольно хорошо.
Чтобы минимизировать несоответствия из-за небольших вариаций или ошибок в правописании, я использовал алгоритм Metaphone, а затем расстояние Левенштейна (масштабированное до 0-100 в процентном соотношении) в кодировках Metaphone для измерения степени близости. Это, кажется, сработало довольно хорошо.
Используйте индекс FM с возвратом, аналогичный тому, что был в нечетком выравнивателе Боути
Чтобы расширить ответ Cd-MaN, похоже, что вы столкнулись с проблемой нормализации. Не очевидно, как обрабатывать оценки между выравниваниями различной длины.
Учитывая, что вас интересует, вы можете получить p-значения для вашего выравнивания. Если вы используете Needleman-Wunsch, вы можете получить эти p-значения, используя статистику Karlin-Altschul http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
BLAST может провести локальное выравнивание и оценить их, используя эту статистику. Если вы беспокоитесь о скорости, это будет хорошим инструментом для использования.
Другой вариант - использовать HMMER. HMMER использует профили скрытых марковских моделей для выравнивания последовательностей. Лично я считаю, что это более мощный подход, поскольку он также предоставляет информацию о местоположении. http://hmmer.janelia.org/