Алгоритм измерения расстояния между неупорядоченными последовательностями

Question

Расстояние Левенштейна дает нам способ вычислить расстояние между двумя одинаковыми строками в терминах неупорядоченных отдельных символов:

quick brown fox
quikc brown fax

Расстояние Левенштейна = 3.

Что такое похожий алгоритм для расстояния между двумя строками с одинаковыми подпоследовательностями? Например, в

quickbrownfox
brownquickfox

расстояние Левенштейна равно 10, но это не учитывает того факта, что строки имеют две одинаковые подпоследовательности, что делает их более "похожими", чем полностью неупорядоченные слова типа

quickbrownfox
qburiocwknfox

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

Какие существуют меры расстояния, которые учитывают длину подпоследовательностей, не предполагая, что подпоследовательности могут быть легко разбиты на отдельные слова?

Answer 1

Одной простой метрикой было бы взять все n * (n-1) / 2 подстрок в каждой строке и посмотреть, сколько перекрытий. В этом подходе есть несколько простых вариантов, когда вы смотрите только на подстроки определенной длины.

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

Answer 2

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

Answer 3

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

Answer 4

У меня сложилось впечатление, что это NP-полная проблема.

По крайней мере, я не понимаю, как мы можем избежать исчерпывающего поиска. Более того, я даже не вижу, как мы можем проверить данное решение за полиномиальное время.

Answer 5

Начальный удар: используйте алгоритм diff и количество разностей в качестве расстояния