Как определить последовательность ДНК для сравнения с другим - PullRequest
12 голосов
/ 28 апреля 2009

Я надеюсь, что правильно формулирую это, чтобы понять, что я ищу.

Мне нужно сравнить два фрагмента текста. Если две строки похожи, я хотел бы получить очень похожие оценки, если строки очень разные, мне нужны очень разные оценки.

Если я возьму хэш md5 по электронной почте и поменяю один символ, хеш резко изменится, я хочу, чтобы что-то не слишком изменилось. Мне нужно сравнить, насколько похожи две части контента без сохранения строки.

Обновление : сейчас я собираюсь объединить некоторые идеи из различных ссылок, которые предоставили люди. В идеале мне бы понравилась одна функция ввода для создания моего счета, поэтому я использую справочную строку, чтобы всегда сравнивать свои данные с. Я также смотрю на то, как брать символы аски и суммировать их. Все еще читаете все предоставленные ссылки.

Ответы [ 6 ]

10 голосов
/ 28 апреля 2009

Вам нужен алгоритм LCS (см. Также Расстояние Левенштейна ). Вы также можете попробовать Soundex или другой фонетический алгоритм .

6 голосов
/ 28 апреля 2009

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

Это успешно выполняется в информационно-поисковых системах путем обработки документов как N-мерных точек в пространстве . Каждое слово в языке является осью. Расстояние по оси определяется тем, сколько раз это слово появляется в документе. Подобные документы затем «рядом» друг с другом в космосе.

Таким образом, весь документ не нужно хранить, только его количество слов. И обычно самые распространенные слова в языке вообще не учитываются.

1 голос
/ 28 апреля 2009

Многие люди предлагали смотреть на расстояния / метрики, как подходы, и я думаю, что формулировка вопроса ведет к этому. (Кстати, хеш, такой как md5, пытается сделать нечто прямо противоположное метрике, поэтому неудивительно, что это не сработает для вас. Существуют похожие идеи, которые мало меняются при небольших дельтах, но я подозреваю, что они не кодируют достаточно информации для того, что вы хотите сделать)

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

То, что вы ищете, - это скорее проблема кластеризации, когда вы хотите сгенерировать подпись (то есть вектор признаков) из каждого электронного письма, а затем сравнить ее с новыми входными данными. По сути, у вас есть проблема машинного обучения. Решить, что означает «закрыть», может быть непросто. Однако для начала, если предположить, что на самом деле это электронные письма, которые вы просматриваете, вам может быть полезно посмотреть на генерацию функций, выполняемых многими спам-фильтрами, это даст вам (возможно, евклидову, по крайней мере, для начала) пространство измерять расстояния на основе сигнатуры (вектор признаков).

Не зная больше о вашей проблеме, трудно быть более конкретным.

1 голос
/ 28 апреля 2009

Поскольку для расстояния Левенштейна необходимы обе входные строки для получения значения, вам необходимо сохранить все строки.

Однако вы можете использовать небольшое количество строк в качестве маркеров и хранить их только в виде строк.

Затем вы вычислите расстояние Левенштейна от новой строки до каждой из этих строк маркера и сохраните эти значения. Тогда вы можете догадаться, что две строки, которые имеют одинаковое расстояние Левенштейна для всех маркеров, также похожи друг на друга. Вероятно, было бы разумно «спроектировать» эти маркеры таким образом, чтобы их их взаимное расстояние Левенштейна было как можно большим. Я не знаю, проводились ли какие-либо исследования в этом направлении.

1 голос
/ 28 апреля 2009

Мне нужно сравнить два фрагмента текста. Если две строки похожи, я хотел бы получить очень похожие оценки, если строки очень разные, мне нужны очень разные оценки.

Это действительно зависит от того, что вы подразумеваете под "одинаковыми" или "разными". Например, если кто-то заменит «Соединенные Штаты Америки» на «США» в вашей строке, то будет ли это в основном та же самая строка (потому что США - это просто сокращение для чего-то более длинного), или это будет совсем другое (потому что изменилось много символов )

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

1 голос
/ 28 апреля 2009

Проверьте их Расстояние Левенштейна

В PHP у вас даже есть функция levenshtein () , которая делает именно это.

...