Нахождение интересных анаграмм

Скажем, что и b 1 b 2 … b n - две строки одинаковой длины. Anagramming из двух строк является взаимно однозначное отображение р : [ 1 ... п ] → [ 1 ... п ] такое , что я = Ь р ( я ) для каждого I .$a_1a_2\ldots a_n$$b_1b_2\ldots b_n$$p:[1\ldots n]\to[1\ldots n]$$a_i = b_{p(i)}$$i$

Для одной пары строк может быть несколько анаграмм. Например, если `abcab` и b =, мы имеем p 1 [ 1 , 2 , 3 , 4 , 5 ] → [ 4 , 5 , 1 , 2 , 3 ] и p 2 [ 1 , 2 , 3 , 4 , 5 ] → [ 2 , 5 , $a=$$b=$cabab$p_1[1,2,3,4,5]\to[4,5,1,2,3]$ , среди прочих.$p_2[1,2,3,4,5] \to [2,5,1,4,3]$

Мы скажем, что вес анаграммирования p - это количество срезов, которые нужно сделать в первой строке, чтобы получить куски, которые можно переставить, чтобы получить вторую строку. Формально это число значений i ∈ [ 1 … n - 1 ], для которых p ( i ) + 1 ≠ p ( i + 1 ) . То есть, это количество точек , в которых р вовсе не увеличивает ровно 1.For например, ш ( $w(p)$$p$$i\in[1\ldots n-1]$$p(i)+1\ne p(i+1)$$p$ и w ( p 2 ) = 4 , потому что p 1 разрезаетодин раз на кускии, а p 2 разрезаетчетыре на пять кусков.$w(p_1) = 1$$w(p_2) = 4$$p_1$1234512345$p_2$12345

Предположим, что существует анаграммирование для двух строк и b . Тогда хотя бы одно анаграммирование должно иметь наименьший вес. Скажем так, этот самый легкий . (Может быть несколько самых легких анаграммингов; мне все равно, потому что меня интересуют только веса.)$a$$b$

Вопрос

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

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

мотивация

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

холецистодуоденостомия
дуоденохолецистостомия

Проблема должна быть ясно: это неинтересно , потому что они допускают очень легкий anagramming , что просто обменивает cholecysto, duedenoи stomyсекции, для веса 2. С другой стороны, это намного короче пример гораздо более удивительным и интересным:

береговая линия в
разрезе

Здесь самый легкий анаграмминг имеет вес 8.

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

Эта проблема известна как «проблема минимального общего разделения строк». (Точнее, ответ в задаче минимального общего разделения строк равен ответу в вашей задаче плюс 1). К сожалению, это NP-сложный, даже с ограничением, которое каждая буква встречается не более двух раз в каждой из входных строк, что доказано Гольдштейном, Килманом и Чжэн [GKZ05]. Это означает, что никакого алгоритма полиномиального времени не существует, если P = NP. (Конечно, если каждая буква встречается не более одного раза, тогда проблема тривиальна, потому что есть только одно анаграммирование.)

С другой стороны, те же авторы [GKZ05] приводят алгоритм полиномиального времени в 1.1037-приближении с тем же ограничением. («Алгоритм аппроксимации 1.1037 » означает алгоритм, который может не выводить правильный ответ A, но гарантированно выдает значение B такое, что A ≤ B ≤ 1.1037 A. ) Они также дают алгоритм 4-аппроксимации линейного времени под Более слабое ограничение: каждая буква встречается не более трех раз в каждой из входных строк.

[GKZ05] Авраам Гольдштейн, Петр Колман и Цзе Чжэн. Минимальная общая проблема разбиения строки: твердость и приближения. Электронный журнал комбинаторики , 12, статья R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Это продолжение ответа Цуёси Ито, приведенного выше , резюмируя наиболее релевантную часть статьи GKZ05, которую он цитировал.

$G$$(i, j)$$a_i = b_j$$a_{i+1} = b_{j+1}$$(i, j)$$(k, \ell)$$i≤k$$i\mapsto j$$i+1\mapsto j+1$$k\mapsto\ell$$k+1\mapsto\ell+1$

1. $i=k$$j\ne\ell$
2. $i+1=k$$j+1\ne\ell$
3. $i+1<k$$\{j, j+1\}$$\{\ell, \ell+1\}$

$G$$s$$n-s-1$$n$$a$$b$$G$

yttrioustouristyouriououriri$s=2$y|t|t|ri|ou|st|ou|ri|s|t|y

С другой стороны, рассмотрим deraterи treader. На этот раз у графа есть три вершины:

1. DErater + treaDEr
2. dERater + treadER
3. deratER + treadER

$s=2$der|a|t|e|rt|r|e|a|der

Он не охватывает точный алгоритм, который вы имели в виду (что делает ответ Цуёси Ито ), но пытается решить основную проблему поиска «интересных» анаграмм ...

Моей первой мыслью было использование некоторого изменения расстояния редактирования, когда атомные изменения взвешиваются в соответствии с их «интересностью», а не с обычными весами «сложность» или «путаница». Конечно, кажется маловероятным, что вы сможете эффективно кодировать действительно интересные преобразования таким образом, поскольку они, вероятно, будут нелокальными и, следовательно, сталкиваются с проблемами MIS и т. Д. И т. Д.

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

Третья идея - полностью отказаться от рассмотрения структуры самого анаграммирования и вместо этого взглянуть на семантику слов. Часто то, что делает анаграмму «интересной», - это несоответствие значений участвующих слов. Так что попробуйте что-нибудь вроде вычисления их расстояния в WordNet или чего-то подобного.

Задача может быть сформулирована в терминах групп перестановок .

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

Сначала вспомним обозначение для перестановок, а именно так называемое обозначение цикла :

• $()$
• $(1)$
• $(12)$
• $(123)$
• и так один

Эти простые «циклы» составлены для описания более сложных перестановок.

$n$

• $(12)$
• $(a\ b)(a+1\ b+1)$$a>0$$b<a+1$$b+1\le n$
• ...
• $(a\ b)(a+1\ b+1)\cdots(a+i-1\ b+i-1)$$a>0$$a+i-1\le b$$b+i-1\le n$

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

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

Что касается холецистодуоденостомии / дуоденохолецистостома, я заметил, что если бы вы присвоили число каждому персонажу, описывающее, насколько оно было перемещено как дельта, у вас было бы что-то вроде 7 7, затем 8 -7 с, затем 6 0. Это не правильно, потому что некоторые символы могли повторяться (второй c двигался только вперед 2, а не назад 7) и т. Д., Но все еще очень «кодируемо по длине бега», потому что вы видите одни и те же дельты подряд.

Сравните с береговой линией / разрезом, где вы видите что-то вроде (+2) (+ 5) (+ 5) (- 3) (- 1) (+ 3) .... намного меньше "кодируемой длины пробега".

Возможно, случайность дельт может дать вам «оценку» того, насколько интересна анаграмма?