Блог

Чтобы более понятно объяснить свой вопрос, я начну с объяснения реального случая, с которым я столкнулся.

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

1. Я знаю все предложения, которые я хочу отобразить
2. Я хочу найти [одно из] кратчайшего набора УПОРЯДОЧЕННЫХ слов, которое позволяет мне отображать все предложения

Пример:

  SENTENCES:
 "A dog is on the table"
 "A cat is on the table"
 SOLUTIONS:
 "A dog cat is on the table"
 "A cat dog is on the table"
  

Я попытался подойти к этой проблеме с помощью «позиционных правил», определяющих для каждого УНИКАЛЬНОГО слова в наборе ВСЕХ слов, используемых во ВСЕХ предложениях, какие слова должны быть слева или справа от него. В приведенном выше примере набор правил для слова «on» будет «слева (A, dog, cat, is) справа (the, table).

Этот подход работал для тривиальных случаев, но в моей реальной ситуации есть две дополнительные трудности, из-за которых я застрял, и обе они связаны с необходимостью повторяющихся слов:

1. В предложении повторения: «кошка на столе» имеет два «the».
2. Циклические ссылки: В наборе из трех предложений «Рыжий кот» «Мой кот на столе» «Этот стол красный», в правилах будет указано, что КРАСНЫЙ должен быть слева от CAT, CAT должен быть слева от TABLE, а TABLE должен быть слева от RED.

ПОЭТОМУ мой ВОПРОС:

Какой класс алгоритмов (или даже лучше: каков конкретный алгоритм) изучает и решает такого рода проблемы? Не могли бы вы опубликовать какую-нибудь ссылку или пример кода на нее?

РЕДАКТИРОВАТЬ: Уровень сложности

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

1. У меня есть около 1500 предложений, которые я хочу представить.
2. Все предложения по сути являются модификациями ограниченного пула из ~ 10 предложений, где меняется всего несколько слов. Основываясь на предыдущем примере, это немного похоже на то, что все мои предложения будут говорить либо о «положении чьего-то питомца относительно предмета мебели», либо о «физическом описании чьей-то мебели».
3. Количество уникальных слов, используемых для построения всех предложений, равно <100.
4. Предложения не более 8 слов.

Для этого проекта я использую python, но подойдет любой язык, который можно читать (например: НЕ запутанный perl!).

Заранее благодарю вас за ваше время!

Если я вас правильно понимаю, это эквивалентно кратчайшей общей задаче о суперсеквенции. Эта проблема NP-полная, но существуют алгоритмы аппроксимации. Google выдает несколько статей, включая эту.

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

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

Если эта формулировка эквивалентна вашей проблеме, то это означает, что ваша проблема действительно NP-полная, поскольку выравнивание множественных последовательностей является NP-полным, хотя существует множество эвристических алгоритмов, которые выполняются за разумное время. К сожалению, большинство алгоритмов MSA предназначены для работы с символами ДНК или последовательностями белка, а не со словами английского языка.

Пример

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

Предложение 1: ---- - Рыжий кот -- -- --- ----- -- ---
Предложение 2: ---- Мой - --- кот лежит на столе -- ---
Предложение 3: Это -- - --- --- -- -- --- таблица красного цвета
Консенсус: то, что мой рыжий кот на столе, красный

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

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

Эвристика, которую я бы предложил, заключалась бы в том, чтобы взять пары предложений, решитьhttp://en.wikipedia.org/wiki/Longest_common_subsequence_problem для них (решение для которых находится в стандартной библиотеке Python, найдите difflib) разрешите конфликтующие разделы случайным образом и замените пару этим одним предложением. Проделайте это со всеми вашими предложениями, и у вас будет приемлемое решение. Не самый лучший, но подходящий.

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

После недели so кодирования (это хобби-проект) Я решил ответить на свой собственный вопрос. Это не потому, что ответы, которые я ранее получил, были недостаточно хорошими, а скорее потому, что я использовал их три для кодирования решения, которое я хотел, и мне показалось неправильным отдавать должное только одному из ответчиков, поскольку я действительно использовал ввод данных тремя из них, чтобы придумать удовлетворительное решение.

Давайте начнем с конца: предложенная мной эвристика дает очень удовлетворительные результаты (по крайней мере, для реального случая, для которого я ее использую). У меня было 1440 предложений, в среднем по ~ 6 слов в каждом, с использованием набора из 70 уникальных слов. Выполнение программы занимает около 1 минуты и предоставляет мне дополнительную последовательность всего из 76 слов (на 10% больше, чем «физический» [но не «логический»] нижний предел проблемы).

Эвристика действительно адаптирована к моему реальному случаю, в частности, к тому факту, что большинство предложений построено вокруг примерно 10 «прототипов» (см. Пункт № 2 моей правки в вопросе) и состоит из четырех последовательных шагов:

1. Изоморфное сжатие
2. Уменьшение сходства
3. Оптимизация с грубой избыточностью
4. Точная оптимизация избыточности

Изоморфное сжатие

Я определил как «изоморфные» два предложения A и B, такие, что преобразование A в B и B в A потребовало бы точно таких же шагов. Пример:

 'A dog is on the carpet'
'A cat is under the table'
  

Преобразование всегда требует замены слов в позиции 1, 3, 5 первой строки словами в позиции 1, 3, 5 второй.

Группировка предложений в «изоморфные семейства» позволяет легко создавать оптимизированные суперструны, просто вставляя в общий корень "A __ is __ the __" список переменных элементов для позиции 1, 3, 5.

Уменьшение сходства

На этом этапе процесса количество предложений резко сократилось (обычно имеется смесь примерно из 50 дополнительных последовательностей из изоморфных семейств и бесхозных предложений, которые не были изоморфны ни одному другому в пуле). Программа анализирует этот новый пул и объединяет две наиболее похожие строки, затем повторяет процедуру для нового набора, составленного из результата слияния и строк, которые еще не были объединены, и так далее, пока все не будет объединено в одну дополнительную последовательность.

Оптимизация с грубой избыточностью

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

Точная оптимизация избыточности

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

 aaa xxx bbb ccc ddd eee xxx fff
  

программа попытается сдвинуть два xxx слова друг к другу:

 aaa bbb xxx ccc ddd eee xxx fff
aaa bbb xxx ccc ddd xxx eee fff
aaa bbb ccc xxx ddd xxx eee fff
  

если дополнительная последовательность достигает:

 aaa bbb ccc xxx xxx ddd eee fff
  

и ни одно предложение не использует оба вхождения xxx одновременно, тогда одно из двух xxx может пойти.

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

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

ЗАКЛЮЧИТЕЛЬНОЕ ЗАМЕЧАНИЕ: Как только программа будет завершена / проект завершен (в худшем случае через пару месяцев), я выпущу его под GPL и добавлю ссылку на репозиторий кода в исходном вопросе. Я считаю, что пометка вопроса как «избранного» должна уведомлять маркер о любом редактировании…. на всякий случай, если вас интересует реальный код, конечно!