Существует ли алгоритм редактирования расстояния, который учитывает «транспонирование фрагментов»?

Question

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

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

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

Turing, Alan.

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

Alan Turing

ближе, чем соответствует

Turing Machine

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

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

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

Одна из самых простых и эффективных современных альтернатив для редактирования расстояния называется нормализованным расстоянием сжатия, или NCD. Основная идея легко объяснить. Выберите популярный компрессор, который реализован на вашем языке, например zlib . Тогда для данной строки A и строки B пусть C (A) будет сжатым размером A и C ( B) будет сжатым размером B . Пусть AB означает « A , соединенный с B », так что C (AB) означает «сжатый размер» A , объединенный с B". Далее вычисляется дробь

( C (AB) - мин ( C (A) , * 1032). * C (B) )) / макс ( C (A) , C (B) )

Это значение называется NCD ( A * 1040) *, B ) и измеряет сходство, аналогичное расстоянию редактирования, но поддерживает больше форм сходства в зависимости от того, какой компрессор данных вы выбираете. Конечно, zlib поддерживает описываемое вами сходство стиля "чанк". Если две строки Аналогично сжатый размер конкатенации будет близок к размеру каждого отдельно, поэтому числитель будет близок к 0, а результат будет близок к 0. Если две строки очень разные, сжатый размер вместе будет примерно равна сумме добавленных сжатых размеров. и поэтому результат будет около 1. Эту формулу гораздо проще реализовать, чем редактировать расстояние или почти любые другие объяснения. t Строка мера сходства, если у вас уже есть доступ к программе сжатия данных, такой как zlib. Это потому, что большая часть «тяжелой» работы, такой как эвристика и оптимизация, уже была выполнена в части сжатия данных, и эта формула просто извлекает количество похожих шаблонов, найденных с помощью общей теории информации, которая не зависит от языка. Более того, этот метод будет намного быстрее, чем большинство явных мер сходства (таких как расстояние редактирования) для описанного вами диапазона размеров в несколько сотен байт. Для получения дополнительной информации об этом и примере реализации просто выполните поиск Normalized Compression Distance (NCD) или посмотрите на следующий проект бумаги и github: http://arxiv.org/abs/cs/0312044 "Кластеризация сжатием" https://github.com/rudi-cilibrasi/libcomplearn Реализация языка C

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

Answer 4

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

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

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

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

Answer 5

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

Answer 6

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