Алгоритм беспорядка строк относительно последовательностей и порядка подстрок (строки одинаковой длины, одинаковые символы, уникальные символы, без лексического значения)

Question

Допустим, у меня есть "peachz" в качестве строки, а "eachzp" и "pahezc" в качестве попыток, использованных для сравнения.

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

Вот пример изображения:
http://i51.tinypic.com/1zz2c10.png http://i51.tinypic.com/1zz2c10.png

"eachzp"имеет тот же порядок символов, за исключением P. Поскольку P переместился на первую позицию, все остальные символы рассматриваются как одна позиция не на своем месте.«eachzp» выдаст степень беспорядка 10, а полностью зашифрованная попытка «pahezc» выдаст 8. Это неверно.Такие вещи, как расстояние Хэмминга или Левенштейна, также не принимают во внимание эти «последовательности порядка».

Мой вопрос: существует ли алгоритм, который я могу использовать для вывода беспорядка / подобия строк, учитывая относительный порядоких персонажи?

(Это не должно быть связано со словарем, поскольку строки не являются словами и не имеют лексического значения. Если это поможет, символы также будут уникальными в каждой строке.)

tia

/ edit: я попытаюсь объяснить мою ситуацию по-другому, пытаясь уточнить ее:

• Строки всегда имеют одинаковую длину

• Строки всегда имеют одинаковые символы (например, если оригинал был "ors", другие строки могут быть только "ors", "osr", "sor", "ros", "sro" или "rso" - одинаковая длина и одинаковые символы)

• Символы всегда уникальны для каждой строки

• Строкине слова и не имеют никакого лексического значения

• Мне нужен алгоритм, чтобы учесть последовательность заказа.Если исходная строка «peachz», «eachzp» упорядочен почти точно так же, только «p» неуместно.Это должно быть больше похоже на «peachz», чем «pahezc», который намного более закручен, и во всех направлениях (я чувствую, что это понятие «направления» может иметь отношение к решению).

• "eapchz" также должен быть менее зашифрованным, чем "eachzp".В обеих ситуациях только буква «p» неуместна, но она на более коротком расстоянии от «eapchz».

Вся помощь приветствуется.спасибо

Answer 1

Это звучит как проблема подсчета инверсий в массиве; по ссылке вы найдете описания алгоритма «разделяй и властвуй» O (n log n), похожего на mergesort.

В задаче инверсии у вас есть массив, подобный 1 3 2 5 4, и вы хотите измерить, насколько он не в порядке по сравнению с 1 2 3 4 5. Итак, 1 2 3 4 5 - аналог вашего "peachz ", и если мы присвоим 1 для 'p', 2 для 'e' и т. д., они будут той же проблемой. Инверсия - это любая пара элементов, которые не в порядке (необязательно смежные элементы).

Возможно, вам понадобится мера, отличная от числа инверсий. Моим лучшим предположением будет вращение счет, где вращение удаляет элемент из одной позиции и вставляет его в другое место. Например, «eachzp» находится всего в одном обороте от «peachz». Я думаю, что вы могли бы считать вращения с помощью алгоритма динамического программирования O (n ^ 2), такого как расстояние Левенштейна, хотя я не проверял это ..

Answer 2

Если я правильно понимаю ваш вопрос, вы ищете метрику расстояния Кендалла-Тау. Вы можете прочитать об этом здесь .

Answer 3

Редактировать: Совершенно новый алгоритм.

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

1. Найти все подстроки зашифрованной строки максимальной длины, которые соответствуют исходной строке, ихранить их в массиве в указанном порядке.Примечание: поскольку каждая буква появляется только один раз, подстроки будут непересекающимися.
2. Пусть «оценка фрагментации» будет числом максимальных подстрок.
3. Пусть «оценка непрерывности» будет суммойквадраты длин подстрок.
4. Для каждой подстроки, оцените ее, сравнивая ее с общим порядком подстрок (сложите, сколько предшествующих ей должно и сколько следует за этим, что должно).Пусть строка "order order" будет суммой всех оценок подстрок.
5. Теперь у нас есть трехмерная оценка.Сравните строки, сначала сравнивая оценку фрагментации, если они равны, сравнивают оценку непрерывности, если они равны, сравнивают оценку порядка.Более низкие оценки фрагментации менее зашифрованы, более высокие оценки непрерывности и порядка менее зашифрованы.

Пример: «acpehz» имеет оценки фрагмента, продолжение и порядка 3, 12, 4.

С помощью этого метода мы получаем «peachz» <«eachzp» <«pahezc», если хотите. </p>

Единственные очевидные ограничения, которые я могу придумать для этого алгоритма, это то, что он, вероятно, будет очень медленным и «eachzp"менее зашифрован, чем" pezach ", даже если вы думаете, что они равны, поскольку" только одна буква вышла из строя ".