Английская панграмма - это предложение, которое содержит все 26 букв английского алфавита. Самая известная английская панграмма - это, вероятно, «Быстрая коричневая лисица перепрыгивает через ленивую собаку». Моя любимая панграмма - «Удивительно мало дискотек предоставляют музыкальные автоматы».

идеальная панграмма - это панграмма, в которой каждая буква встречается только один раз. Я нашел несколько источников в Интернете, в которых перечислены известные идеальные панграммы. Кажется, что никто не пытался успешно создать их все в полном объеме, поэтому я принял это как забавную задачу. Так я нашел все * идеальные панграммы английского языка. Я объясню звездочку позже.

Вот некоторые из моих любимых идеальных панграмм, которые я обнаружил

  • Crwth вокс заглушает ци в тренажерном зале fjeld койка. (Звук кельтской скрипки поражает восточный фитнес-центр, ориентированный на духовные силы, расположенный на бесплодном плато Скандинавии.) Это все юридические слова Scrabble!
  • Squdgy kilp job zarf nth cwm vex. (Плохо сформированные водоросли покупают декоративный подогреватель чашек, который раздражает одна из многих полуоткрытых ям с крутыми склонами в начале долины или склона горы.)
  • Нимфы-качки, вакф, наркотики, блиц. (Благотворительное пожертвование опьянило лесных духов, которые расстроили атлета, участвующего в нападении.)
  • Хм, фьордовый вальс, чинк буск, питекс вегетарианец. (Посмотрим, длинный узкий и глубокий вход танцует, пятерка на костях играет музыку на улице, а маленький круглый контейнер для больных и недееспособных отдыхает.) Также Scrabble разрешен, но имеет междометие (Hm ).

К сожалению, это одни из самых разборчивых предложений, которые мне удалось найти *. Все идеальные панграммы, сгенерированные из Официального турнира и Club Word List 3 (OWL3) для Scrabble без междометий, содержат слово cwm или crwth. Waqf - это разрешенный турнир по Scrabble за пределами Северной Америки.

Как найти все идеальные панграммы

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

Шаг 1: поиск наборов слов для идеальной панграммы

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

Я начал со словаря Unix, который представляет собой свободно доступный список английских слов, который поставляется практически со всеми операционными системами на основе Unix. Я сразу заметил, что в списке есть проблемы с качеством. Во-первых, каждая буква алфавита считалась словом в словаре Unix, и в него входило множество не-слов, например «vejoz». Это продемонстрировало необходимость черного списка для управления списками слов, найденных в Интернете. Во-вторых, в словаре Unix не хватало слов во множественном числе, поэтому словарь должен был включать слово «оранжевый», но не «апельсины». Список слов настолько ограничен, что ни одна ранее известная идеальная панграмма не включала только слова из словаря Unix. Я все еще нашел некоторые, например «s qudgy kilp job zarf nth cwm vex».

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

Наконец, после многих итераций я заплатил 15 долларов, чтобы купить пробное членство в Североамериканской ассоциации игроков Scrabble®, что дало мне доступ к проприетарному и защищенному авторским правом OWL3, который является источником некоторых противоречий. Даже тогда мне пришлось добавить некоторые известные английские слова, например, однобуквенные слова а и я.

Вооружившись правильным списком слов, я реализовал алгоритм для создания всех наборов слов из этого списка, каждое из которых содержит одну букву каждой буквы английского алфавита. Я подробно опишу алгоритм в разделе «Алгоритм» ниже.

Шаг 2. Формирование английских предложений из набора слов

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

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

  1. Должен быть хотя бы один глагол.
  2. Может быть только на одно существительное больше, чем глаголов, за исключением союза или предлога, которые встречаются очень редко.
  3. Если есть прилагательные, то должны быть и существительные.

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

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

Алгоритм

Этот раздел носит технический характер, но, надеюсь, его легко понять. Не стесняйтесь переходить к разделу «Результаты и выводы».

Стратегия высокого уровня

Цель состоит в том, чтобы создать все возможные наборы слов из данного списка слов, который «идеально» охватывает английский алфавит.

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

1. Очистка списка, также известная как канонизация.

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

  1. Удалите все пробелы вокруг слова и преобразуйте его только в нижний регистр
  2. Убедитесь, что слова содержат только буквы английского алфавита; Я использовал простой фильтр регулярных выражений: /^[a-z]+$/
  3. Фильтр против любых других списков, например черные списки; если слово находится в черном списке, пропустите это слово
  4. Удалить все слова с повторяющимися буквами

Это значительно сократило пространство поиска со списков из 200 000 ~ 370 000 слов до гораздо меньших 35 000 ~ 65 000 слов.

2. Использование битовых масок

Битовые маски - это целочисленные представления состояний. У битовых масок есть несколько преимуществ:

  • Битовые маски хорошо представляют эту проблему. Порядок букв не имеет значения, поэтому все комбинации слов могут быть представлены в виде серии из 26 цифр, состоящей из нулей и единиц, причем каждая цифра указывает, существует ли буква в комбинации. Например. если набор слов содержит букву «е», пятая цифра будет 1, в противном случае - 0.
  • Битовые маски эффективны: поскольку пространство поиска постоянно, битовые маски обеспечивают эффективное хранение и представление всех возможных комбинаций букв. Кроме того, побитовые операции выполняются быстро; чтобы проверить, можно ли объединить две битовые маски для получения большей битовой маски, проверьте, равно ли побитовое И двух масок 0, причем обе эти операции являются чрезвычайно быстрыми операциями.

Итак, превратите каждое слово в битовую маску, которую можно представить как целое число. Например, слово «cab» отображается на битовую маску 111, которая является десятичным числом 7. Слово «be» отображается на 10010, десятичное число 18, и так далее. Наибольшая возможная битовая маска - это маска со всеми буквами алфавита, возможное состояние идеальной панграммы, 11111111111111111111111111, которое является десятичным числом 67 108 863 или 2²⁶ -1. Это хорошо вписывается в стандартное 32-битное целое число со знаком, которое может представлять до 2³¹-1.

Использование битовых масок еще больше сжимает пространство, поскольку анаграммы из одного слова отображаются в одну и ту же битовую маску. И «печь», и «ссылка» отображаются на маску 10110100000000, которая представляет собой десятичное число 11520. Это дополнительно сокращает пространство поиска с 35000 до 65000 слов до 25000–45000 битовых масок.

Сохраните отображение битовой маски обратно в набор слов, из которых они получены. Это будет полезно при выводе наборов слов.

3. В поисках идеальной панграммы с помощью динамического программирования

Суть алгоритма довольно проста:

Учитывая возможное состояние (которое состоит из допустимых комбинаций существующих слов), попробуйте все маски из начального списка слов, чтобы увидеть, возможно ли создать новое допустимое состояние (путем проверки, равно ли побитовое И состояния и маски 0, что означает отсутствие перекрывающихся букв). Создайте новое состояние, используя операцию побитового ИЛИ, которая объединяет все единицы вместе. Для каждого нового обнаруженного состояния повторяйте, пока не останется неисследованных состояний. Если это доходит до конца, это означает, что алгоритм нашел по крайней мере один возможный идеальный набор слов панграммы. Первым возможным состоянием, которое может перечислить все возможные состояния, является пустое состояние или 0, где буквы алфавита не включены. Итак, начните здесь, а затем рекурсивно обнаруживайте, какие состояния возможны.

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

Итак, создайте массив размером 2²⁶ от 0 до 67 108 863 включительно. Каждый индекс представляет состояние битовой маски, как объяснялось ранее. Значение каждого индекса массива представляет то, что известно о состоянии. 0 означает, что состояние либо нет, либо недоступно. 1 означает, что государство нашло способ достичь возможного состояния идеальной панграммы. -1 означает, что государство не нашло способа достичь конца.

Псевдокод ниже:

int PANGRAM_STATE;  // 2^26 - 1 == 67108863
// dp[state] == 0  means the state is untouched or unreachable
// dp[state] == 1  means the target is reachable from state
// dp[state] == -1 means the target is unreachable from state
int solve(int state, int target, int[] dp, List<Integer> masks) {
    if (state == target) {  // Base Case: Does it reach the target?
        return 1;
    }
    if (dp[state] != 0) {  // DP: don't repeat work for a state
        return dp[state];
    }
    boolean reachesTarget = false;
    for (int mask : masks) {  // try all masks
        if ((state & mask) != 0) {  // check for overlap
            continue;
        }
        int newState = state | mask;  // combine state and masks
        dp[newState] = solve(newState, target, dp, masks);
        if (dp[newState] == 1) {
            reachesTarget = true;
        }
    }
    return reachesTarget ? 1 : -1;
}
solve(0, PANGRAM_STATE, dp, masks);

Интерлюдия: сложность и практический анализ времени выполнения

Для серии из 26 бит существует 2² возможных битовых маски. Поскольку каждое состояние обрабатывается только один раз из-за мемоизации, время выполнения этого алгоритма равно O (n 2 ^ d), где d - это размер алфавита - 26. Переменная n обозначает не количество слов, а количество битовых масок. С 67 108 863 и примерно 45 000 битовых масок получается порядка 3 триллионов, с которыми мой MacBook Pro мог справиться примерно за 45 минут; поддается любому современному компьютеру. Также стоит отметить, что стек рекурсивных вызовов никогда не будет глубже 26 (скорее всего, никогда не станет глубже 15), поэтому им также легко управлять из этого измерения.

Одним из преимуществ подхода с использованием битовой маски только с двумя состояниями является то, что все состояния могут быть сохранены в памяти. Поскольку в каждом состоянии есть только 3 значения (-1, 0, 1), их можно сохранить в одном байте. Из одного байта на состояние, 2²⁶ состояния составляют около 67 мегабайт, что опять-таки очень удобно.

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

4. Динамическое построение направленного ациклического графа (DAG).

Теперь, когда мы заполнили состояния битовой маски, пора найти решение!

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

Чтобы отслеживать отношения между состояниями, цель состоит в том, чтобы создать направленный ациклический граф (DAG), который определяет, какие промежуточные состояния составляют любое данное состояние. Группы DAG легко перемещать для получения выходных данных, особенно из-за их нециклической природы. Чтобы построить, начните с возможного состояния идеальной панграммы и создайте направленный край (стрелку), который указывает на промежуточные состояния, составляющие его. Повторите процесс с промежуточными состояниями, и он создаст DAG. Циклов никогда не будет, потому что стрелки всегда указывают на состояние с меньшим значением.

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

5. Распечатайте плоды своего труда в виде дерева!

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

int PANGRAM_STATE;  // 2^26 - 1 == 67108863
Map<Integer, List<Integer>> edges;  // DAG edges
Map<Integer, List<String>> maskMap;  // Mask back to word list
void outputTree(int level, int state, Map edges, Map maskMap) {
    output.indent(level);  // uniformly indent based on level
    output.print(state);
    if (maskMap.containsKey(state)) {
        output.print("====>");
        output.print(maskMap.get(state));
    }
    for (int substate : edges.get(state)) {
        int composite = state ^ substate;
        outputTree(level + 1, substate, edges, maskMap);
        outputTree(level + 1, composite, edges, maskMap);
    }
}
outputTree(0, PANGRAM_STATE, edges, maskMap);

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

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

Результаты и уроки

Произведены деревья Pangram!

Не стесняйтесь пройтись по идеальным панграмным деревьям, чтобы увидеть, сможете ли вы найти интересные предложения!

Https://github.com/temporalparts/PerfectPangrams

Есть много возможных идеальных панграм

Я был удивлен количеством возможных идеальных панграм. Много! Лучшая стратегия их объединения не требует сложного процессора естественного языка. После того, как слова-кандидаты были помечены как подходящие для существительного или глагола, набор слов должен содержать по крайней мере одно существительное, один глагол и правильное соотношение существительных и глаголов.

Качество данных - сложная проблема

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

Правила идеальных панграм

Есть много нюансов относительно того, что можно считать идеальным панграмом! Я хотел искать панграммы без каких-либо междометий (например, hm, pht), но есть и другие популярные ограничения, такие как сокращения, акронимы, сокращения, инициалы, отдельные буквы, существительные собственные и римские цифры. Есть также слова, являющиеся названиями букв, например Qoph, которые, как мне кажется, являются обманом.

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

Звездочка

Звездочка на месте, потому что определение всех идеальных панграмм английского языка не совсем точно. Есть нюансы, связанные с тем, что следует допускать в идеальных панграммах английского языка. Также существует множество споров относительно того, являются ли некоторые слова английскими. Учитывая эти нюансы, действительно сложно сказать, что я нашел все идеальные панграммы. Я могу достаточно уверенно сделать два утверждения:

  1. Я нашел методику создания всех идеальных панграм английского и других языков с похожими или меньшими наборами символов.
  2. Я перечислил все наборы слов, которые могут образовывать идеальные панграммы, используя официальный словарь турниров Scrabble, OWL3.

Не стесняйтесь создавать свои собственные идеальные панграммы с помощью техник, описанных в этом посте!

Зависимость Perfect Pangrams от слов валлийского и арабского происхождения

Слова, производные от валлийского и арабского языков, были действительно важны для существования идеальных английских панграм (если не были ослаблены ограничения идеальной панграммы). Используя список слов OWL3 со строгими правилами относительно идеальных панграмм, не существует идеальных панграм, в которых бы не было слов «cwm (s)» или «crwth (s)». , оба валлийских слова. В международном языке Scrabble производное арабское слово «waqf (s)» является допустимым словом, которое может создавать идеальные панграммы, не прибегая к «cwm (s)» или «Crwth (s)».

Эффективность рабочего потока

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

Расширение / Обобщение - Поиск анаграмм

Идеальный поиск по панграмме также эквивалентен поиску анаграмм для строки «abcdefghijklmnopqrstuvwxyz». Что, если вы хотите создать универсальный поисковик анаграмм?

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

Языки с большими алфавитами

Этот подход и решение линейны по размеру набора слов, но экспоненциальны по размеру алфавита. Этот подход может не работать с большим набором символов, например, с современным японским языком, в котором 46 слоговых слов. 2⁴⁶ равно 70 368 744 177 664; более чем в миллион раз больше, чем английское поисковое пространство 2²⁶ = 67 108 864.

Не совсем понятно, подойдет ли такой подход для японцев. Если японский язык имеет достаточно низкую энтропию, что возможно, этот подход был бы жизнеспособным. Вместо инициализации массива размером 2⁴⁶ состояния будут отслеживаться на карте. Кроме того, можно использовать структуру японского языка; например, кана を (wo) почти исключительно используется как пост-позиционное причастие, и его можно исключить из поиска, уменьшая пространство поиска.

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

Вдохновение

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

Излишне говорить, что поиск идеальных панграмм не дает возможности улучшить нижнюю границу хроматического числа плоскости.

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

Спасибо

Я очень благодарен моим прекрасным друзьям, которые помогли мне вычитать и поправить это, особенно Анне Цзэн, Кэтрин Гао, Дэнни Вассерману, Джорджу Вашингтону и Нику Ву!