Приближенные алгоритмы сопоставления строк
Здесь, на работе, нам часто нужно найти строку из списка строк, которая наиболее близка к некоторой другой входной строке. В настоящее время мы используем алгоритм Needleman-Wunsch. Алгоритм часто возвращает много ложных срабатываний (если мы устанавливаем минимальный балл слишком низко), иногда он не находит совпадения, когда он должен (когда минимальный балл слишком высок) и, в большинстве случаев, нам нужно проверить результаты вручную. Мы думали, что мы должны попробовать другие альтернативы.
Есть ли у вас опыт работы с алгоритмами? Вы знаете, как алгоритмы сравниваются друг с другом?
Я бы очень признателен за совет.
- Android: что-то лучше, чем андроид: ellipsize = "end", чтобы добавить "..." в укороченные длинные строки?
- Соответствие строк с помощью шаблона
- байты строки в java?
- Удаление конечного символа новой строки из входа fgets ()
- \ r \ n, \ r, \ n в чем разница между ними?
PS: Мы кодируем на C #, но вам это не нужно – я спрашиваю об алгоритмах в целом.
О, извините, я забыл упомянуть об этом.
Нет, мы не используем его для сопоставления повторяющихся данных. У нас есть список строк, которые мы ищем – мы называем его поисковым списком. И тогда нам нужно обрабатывать тексты из разных источников (например, RSS-каналы, веб-сайты, форумы и т. Д.) – мы извлекаем части этих текстов (для этого есть целые наборы правил, но это неуместно), и нам нужно сопоставить те против списка поиска. Если строка соответствует одной из строк в списке поиска – нам нужно сделать дальнейшую обработку вещи (что также не имеет значения).
Мы не можем выполнить нормальное сравнение, потому что строки, извлеченные из внешних источников, в большинстве случаев, include некоторые дополнительные слова и т. Д.
Во всяком случае, это не для двойного обнаружения.
- Как мне обойти проблему «» в sqlite и c #?
- Поиск подстроки в объекте NSString
- Что именно делает метод .join ()?
- Как разбить строку на строки и включить разделители с помощью .NET?
- C # string replace не работает
- Как использовать sed / grep для извлечения текста между двумя словами?
- То, что strcmp () точно возвращается в C?
- Преобразование строки в GregorianCalendar
OK, Needleman-Wunsch (NW) – classический сквозной («глобальный») выравниватель из литературы по биоинформатике. Это было давно доступно как «align» и «align0» в пакете FASTA. Разница заключалась в том, что версия «0» не была столь же предубежденной в том, чтобы избегать конечного разрыва, что часто позволяло лучше поддерживать качественные внутренние матчи. Смит-Ватерман, я подозреваю, что вы знаете, является локальным выравнивателем и является исходной основой BLAST. У FASTA был собственный локатор, который немного отличался. Все это, по сути, эвристические методы оценки расстояния Левенштейна, соответствующего метрике оценки отдельных пар персонажей (в биоинформатике, часто даваемой Dayhoff / «PAM», Henikoff & Henikoff или других matrixх и обычно заменяемой чем-то более простым и разумным образом отражающим замены в языковой морфологии слов применительно к естественному языку).
Давайте не будем ценить этикетки: расстояние Левенштейна, как указано на практике, по крайней мере, в основном на расстоянии редактирования, и вы должны оценить его, потому что его невозможно вычислить в целом, и это дорого вычислять точно даже в интересных особых случаях: вода там происходит очень быстро, и поэтому у нас есть эвристические методы долгой и хорошей репутации.
Теперь о вашей собственной проблеме: несколько лет назад мне приходилось проверять точность коротких прочтений ДНК относительно ссылочной последовательности, которая, как известно, была правильной, и я придумал то, что я назвал «привязанные выравнивания».
Идея состоит в том, чтобы взять ваш набор опорных строк и «переварить» его, найдя все местоположения, где встречается соответствующая подстрока 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 ( запись в Wikipedia в agrep ), алгоритмы соответствия биологической последовательности FASTA и BLAST . Это специальные случаи приближенного сопоставления строк , также в репозитории алгоритма Stony Brook . Если вы можете указать, как строки отличаются друг от друга, вы, вероятно, можете сосредоточиться на индивидуальном алгоритме. Например, Aspell использует некоторый вариант «звукового» (soundex-metaphone) расстояния в сочетании с «клавиатурным» расстоянием для размещения плохих заклинателей и плохих типов.
Мы используем метод расстояния Levenshtein для проверки дубликатов клиентов в нашей базе данных. Это работает очень хорошо.
Используйте FM-указатель с Backtracking, похожий на тот, что в Bowtie fuzzy aligner
Чтобы свести к минимуму несоответствия из-за небольших изменений или ошибок в орфографии, я использовал алгоритм Metaphone, а затем расстояние Левенштейна (масштабированное до 0-100 в процентном соотношении) в кодировках Metaphone для некоторой близости. Кажется, это сработало довольно хорошо.
Чтобы расширить ответ Cd-MaN, это звучит так, будто вы столкнулись с проблемой нормализации. Неясно, как обрабатывать оценки между выравниваниями с различной длиной.
Учитывая то, что вас интересует, вы можете захотеть получить p-значения для вашего выравнивания. Если вы используете Needleman-Wunsch, вы можете получить эти p-значения, используя статистику Karlin-Altschul http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
BLAST будет выполнять локальное выравнивание и оценивать их с использованием этих статистических данных. Если вас беспокоит скорость, это будет хорошим инструментом для использования.
Другой вариант – использовать HMMER. HMMER использует профиль Hidden Markov Models для выравнивания последовательностей. Лично я считаю, что это более мощный подход, поскольку он также предоставляет позиционную информацию. http://hmmer.janelia.org/