Есть ли алгоритм расстояния редактирования, который учитывает транспонирование фрагментов?

Я заключил «перестановку фрагментов» в кавычки, потому что не знаю, каким должен быть технический термин. Было бы очень полезно просто знать, есть ли у процесса технический термин.

В статье в Википедии о дистанции редактирования дается хорошее представление об этой концепции.

Принимая во внимание "перестановку фрагментов", я имею в виду, что

Turing, Alan.

должен соответствовать

Alan Turing

точнее, чем соответствует

Turing Machine

Т.е. расчет расстояния должен определять, когда подстроки текста просто перемещались внутри текста. Это не относится к общей формуле расстояния Левенштейна.

Строки будут состоять максимум из нескольких сотен символов - это имена авторов или списки имен авторов, которые могут быть в различных форматах. Я не занимаюсь секвенированием ДНК (хотя подозреваю, что люди, которые это делают, немного знают об этом предмете).


algorithm language-agnostic edit-distance levenshtein-distance
person Steven Huwig    schedule 18.05.2009    source источник
comment
Строки какой длины вы собираетесь сравнивать? Я подозреваю, что точный алгоритм для длинных фрагментов текста будет невозможен.   -  person Noldorin    schedule 18.05.2009
comment
Кроме того, всегда ли эти куски словами?   -  person Noldorin    schedule 18.05.2009
comment
Если под словами вы имеете в виду разделенные пробелами / пунктуацией, возможно, но я не думаю, что хочу на это полагаться. Например, я все еще хочу, чтобы ДиФранко и Ди Франко были близкими людьми, поскольку они находятся в алгоритмах расстояния редактирования.   -  person Steven Huwig    schedule 18.05.2009

Ответы (5)


arrow_upward
2
arrow_downward

Взгляните на метрику расстояния Жаккара (JDM). Это старое, но хорошее дело, которое довольно хорошо разбирается в несоответствиях на уровне токенов, таких как фамилия, имя, фамилия. Для двух сравнений строк расчет JDM - это просто количество уникальных символов, общих для двух строк, деленное на общее количество уникальных символов между ними (другими словами, пересечение над объединением). Например, с учетом двух аргументов «JEFFKTYZZER» и «TYZZERJEFF» числитель равен 7, а знаменатель - 8, что дает значение 0,875. Мой выбор символов в качестве токенов - не единственный доступный, кстати, часто используются н-граммы.

person Community    schedule 19.08.2009

arrow_upward
3
arrow_downward

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

Например, вы можете сначала объединить свои строки, убедившись, что все разделители - это пробелы или что-то еще, что вам нравится, чтобы вы могли сравнить «Алан Тьюринг» с «Тьюринг Алан». Затем разделите одну из строк и выполните алгоритм точного сопоставления строк (например, Horspool -Алгоритм ) с частями против другой строки, подсчитывая количество совпадающих подстрок.

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

В зависимости от вашей среды программирования существует вероятность, что реализация уже доступна. Я лично в последнее время работал с SeqAn, которая представляет собой библиотеку биоинформатики для C ++ и определенно обеспечивает желаемую функциональность.

Что ж, это был довольно абстрактный ответ, но я надеюсь, что он укажет вам правильное направление, но, к сожалению, он не дает вам простой формулы для решения вашей проблемы.

person Paul    schedule 19.05.2009

arrow_upward
1
arrow_downward

Я думаю, вы ищете расстояние Яро-Винклера, которое точно предназначено для сопоставления имен.

person bubaker    schedule 18.05.2009
comment
Кажется, что это выполняет транспонирование символов, но не транспонирование последовательности символов. В моем случае гораздо более вероятно, что имя будет написано правильно, чем в последовательном порядке слов. - person Steven Huwig; 18.05.2009
comment
Хотя он допускает множественные транспозиции, вы правы в том, что он явно не учитывает их в последовательности. Возможно, вы могли бы попробовать предложение преобразовать последовательность слов в символы из этого связанного вопроса SO: http; // stackoverflow.com/questions/828132/levenshtein-distance-how-to-better-handle-words-swapping-positions - person bubaker; 18.05.2009

arrow_upward
1
arrow_downward

Для этого вам может пригодиться расстояние сжатия. См. ответ, который я дал на очень похожий вопрос.

Или вы можете использовать систему подсчета на основе k-кортежей:

  1. Выберите небольшое значение k, например к = 4.
  2. Извлеките все подстроки длины k вашей строки в список.
  3. Отсортируйте список. (O (knlog (n) раз.)
  4. Сделайте то же самое с другой строкой, с которой вы сравниваете. Теперь у вас есть два отсортированных списка.
  5. Подсчитайте количество k-кортежей, общих для двух строк. Если строки имеют длину n и m, это можно сделать за O (n + m) раз, используя слияние списков, поскольку списки отсортированы.
  6. Количество общих кортежей - это ваш показатель сходства.

С маленькими алфавитами (например, ДНК) вы обычно поддерживаете вектор, хранящий счетчик для каждого возможного k-кортежа вместо отсортированного списка, хотя это непрактично, когда алфавит вообще представляет собой любой символ - для k = 4 вы бы нужен массив 256 ^ 4.

person j_random_hacker    schedule 19.05.2009

arrow_upward
0
arrow_downward

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

person tvanfosson    schedule 18.05.2009
comment
Проблема в том, что я хочу использовать его как автоматический классификатор, а не как устройство интерактивных запросов. Кроме того, мой основной вариант использования (одинаковые слова, разный порядок слов и пунктуация) - это простое редактирование, например единственный вызов транспонирования слов в Emacs. :) - person Steven Huwig; 18.05.2009