Существует ли алгоритм редактирования расстояния, который учитывает "транспонирование фрагмента"?
Я помещаю "транспонирование чанков" в кавычки, потому что я не знаю, каким должен быть технический термин. Просто знать, есть ли технический термин для процесса, было бы очень полезно.
Статья в Википедии о расстоянии редактирования дает хорошее представление об этой концепции.
Принимая во внимание "транспонирование фрагментов", я имею в виду, что
Turing, Alan.
должен соответствовать
Alan Turing
ближе, чем соответствует
Turing Machine
Т.е. расчет расстояния должен определять, когда подстроки текста просто перемещаются внутри текста. Это не так с общей формулой расстояния Левенштейна.
Строки будут иметь длину не более нескольких сотен символов - это имена авторов или списки имен авторов, которые могут иметь различные форматы. Я не занимаюсь секвенированием ДНК (хотя я подозреваю, что люди, которые знают, немного узнают об этом предмете).
6 ответов
Посмотрите на метрику расстояния Джакарта (JDM). Это старенький, но приятный персонаж, который довольно хорошо разбирается в расхождениях на уровне токенов, таких как фамилия, имя, фамилия. Для двух строковых сравнений вычисление JDM представляет собой просто число уникальных символов, которые имеют две общие строки, деленное на общее количество уникальных символов между ними (другими словами, пересечение над объединением). Например, учитывая два аргумента "JEFFKTYZZER" и "TYZZERJEFF", числитель равен 7, а знаменатель равен 8, что дает значение 0,875. Мой выбор символов в качестве токенов не единственный доступный, кстати, часто используются и n-граммы.
В случае вашего приложения вы, вероятно, должны подумать об адаптации некоторых алгоритмов из биоинформатики.
Например, вы могли бы сначала объединить ваши строки, убедившись, что все разделители являются пробелами или чем-то еще, что вам нравится, так что вы бы сравнили "Alan Turing" с "Turing Alan". Затем разделите одну из строк и выполните точный алгоритм сопоставления строк (например, алгоритм Хорспула) с частями против другой строки, считая количество совпадающих подстрок.
Если вы хотите найти совпадения, которые просто похожи, но не равны, то что-то по линии локального выравнивания может быть более подходящим, так как оно дает оценку, описывающую сходство, но упомянутый алгоритм Смита-Уотермана, вероятно, немного излишним для вашего приложения и даже не самый лучший из доступных локальных алгоритмов выравнивания.
В зависимости от вашей среды программирования существует вероятность того, что реализация уже доступна. В последнее время я лично работал с SeqAn, который является библиотекой биоинформатики для C++ и определенно обеспечивает желаемую функциональность.
Ну, это был довольно абстрактный ответ, но я надеюсь, что он укажет вам правильное направление, но, к сожалению, он не дает вам простой формулы для решения вашей проблемы.
Одна из самых простых и эффективных современных альтернатив для редактирования расстояния называется нормализованным расстоянием сжатия, или NCD. Основная идея проста для объяснения. Выберите популярный компрессор, который реализован на вашем языке, например zlib. Затем, учитывая строку A и строку B, пусть C(A) будет сжатым размером A, а C(B) будет сжатым размером B. Пусть AB означает " A, соединенный с B ", так что C(AB) означает "Сжатый размер" A, объединенный с B ". Затем вычислите дробь
(C(AB) - мин (C(A), C(B))) / макс (C(A), C(B))
Это значение называется NCD (A, B) и измеряет сходство, подобное расстоянию редактирования, но поддерживает больше форм сходства в зависимости от того, какой компрессор данных вы выберете. Конечно, zlib поддерживает сходство стилей "chunk", которое вы описываете. Если две строки похожи, сжатый размер конкатенации будет близок к размеру каждой отдельной, поэтому числитель будет близок к 0, а результат будет близок к 0. Если две строки сильно отличаются, сжатый размер вместе будет примерно равна сумме добавленные сжатые размеры, и поэтому результат будет близок к 1. Эту формулу гораздо проще реализовать, чем редактировать расстояние или почти любую другую явную меру сходства строк, если у вас уже есть доступ к программе сжатия данных, такой как zlib. Это потому, что большая часть "тяжелой" работы, такой как эвристика и оптимизация, уже была выполнена в части сжатия данных, и эта формула просто извлекает количество похожих шаблонов, найденных с помощью общей теории информации, которая не зависит от языка. Более того, этот метод будет намного быстрее, чем большинство явных мер сходства (таких как расстояние редактирования) для описанного вами диапазона размеров в несколько сотен байт. Для получения дополнительной информации об этом и примере реализации просто выполните поиск Normalized Compression Distance (NCD) или посмотрите на следующий проект бумаги и github:
http://arxiv.org/abs/cs/0312044 "Кластеризация с помощью сжатия"
https://github.com/rudi-cilibrasi/libcomplearn Реализация на языке C
В последнее десятилетие есть много других реализаций и статей по этому вопросу, которые вы можете использовать также на других языках и с изменениями.
Я думаю, что вы ищете расстояние Джаро-Винклера, которое точно соответствует имени.
Вы можете найти расстояние сжатия полезным для этого. Смотрите ответ, который я дал на очень похожий вопрос.
Или вы можете использовать систему подсчета на основе k-кортежей:
- Выберите небольшое значение k, например, k=4.
- Извлеките все подстроки длины-k вашей строки в список.
- Сортировать список. (O(knlog(n) time.)
- Сделайте то же самое для другой строки, с которой вы сравниваете. Теперь у вас есть два отсортированных списка.
- Подсчитайте количество k-кортежей, используемых двумя строками. Если строки имеют длину n и m, это можно сделать за O(n+m) раз, используя объединение списков, поскольку списки расположены в отсортированном порядке.
- Общее число k-кортежей - это ваш показатель сходства.
С маленькими алфавитами (например, ДНК) вы обычно сохраняете вектор, хранящий счетчик для каждого возможного k-кортежа, вместо отсортированного списка, хотя это не практично, когда в алфавите есть любой символ вообще - для k = 4 вы бы нужен массив 256^4.
Я не уверен, что то, что вам действительно нужно, это расстояние редактирования - которое работает просто на строках символов - или семантическое расстояние - выбор наиболее подходящего или похожего значения. Возможно, вы захотите взглянуть на темы в поиске информации, чтобы узнать, как определить, какой из терминов / фраз является наиболее подходящим для данного термина или фразы. В некотором смысле вы сравниваете очень короткие документы, а не строки символов.