すべての*完璧な英語のパングラム
英語のパングラムは、英語のアルファベットの26文字すべてを含む文です。最もよく知られている英語のパングラムは、おそらく「速い茶色のキツネが怠惰な犬を飛び越える」です。私のお気に入りのパングラムは、「驚くほど少数のディスコがジュークボックスを提供します」です。
完璧なパングラムは、各文字が含まれるパングラムです。一度だけ表示されます。私は、既知の完璧なパングラムをリストしているいくつかの情報源をオンラインで見つけました。すべてを網羅的に制作することに成功した人はいないようですので、楽しいチャレンジとして挑戦しました。これが私が英語の完璧なパングラムのすべて*を見つけた方法です。アスタリスクについては後で説明します。
- Crwth vox zaps qi Gym fjeldbunk。 （ケルトのバイオリンの音が、スカンジナビアの不毛の高原にある東部の精神的な力に焦点を当てたフィットネスセンターを襲います。）これはすべてスクラブルの合法的な言葉です！
- Squdgy kilp job zarf nth cwmvex。 （形の悪い昆布は、谷や山腹の頂上にある多くの半開きの急な側面のくぼみの1つがイライラした装飾用のカップウォーマーを購入します。）
- ジョックニンフワクフドラッグベックスブリッツ。 （慈善寄付は、攻撃に従事するアスリートを苛立たせた森の精霊を酔わせました。）
- うーん、フィヨルドワルツ、シンクバスク、ピクスベジ。 （見てみましょう、長くて狭い深い入り江が踊り、サイコロの5つが通りで音楽を作り、病気で休むことができない小さな丸い容器です。）また、スクラブルは合法ですが、感動詞があります（うーん）。
残念ながら、これらは私が見つけた中で最も読みやすい文章の一部です*。感動詞のないスクラブルの公式トーナメントおよびクラブワードリスト3（OWL3）から生成されたすべての完璧なパングラムには、cwmまたはcrwthという単語が含まれています。ワクフは北米以外で合法的なスクラブルトーナメントです。
すべての完璧なパングラムを見つける方法
完璧なパングラムを見つける方法は2つのステップで構成されています。 1つ目は、英語のアルファベットの各文字を含むすべての単語セットを1回検索することです。 2番目のステップは、これらのセットのどれを有効な英語の文に再配置できるかを確認することです。
ステップ1：完璧なパングラムの単語のセットを見つける
次のような単語のセットを見つけ始める英語のアルファベットにまたがるには、英語の単語のリストが必要です。高品質の単語リストを見つけて維持することは、私が予想していたよりもはるかに困難でした。当初、このプロジェクトには2日かかると思っていましたが、このデータ品質の問題により2週間かかることになりました。
無料で入手できる英語の単語リストであるUnix辞書から始めました。これは、ほとんどすべてのUnixベースのオペレーティングシステムに付属しています。リストに品質の問題があることにすぐに気づきました。まず、アルファベットの各文字はUnix辞書で単語と見なされ、「vejoz」などの非単語が多数含まれていました。これは、オンラインで見つかった単語のリストを管理するためのブラックリストの必要性を示しています。 Unix辞書には単語の複数形がないため、辞書には「オレンジ」という単語が含まれますが、「オレンジ」は含まれません。実際、単語リストは非常に制限されているため、これまでに知られている完全なパングラムには、Unix辞書の単語のみが含まれていません。 「squdgykilpjob zarf nth cwm vex」など、いくつかあります。
次に、インターネットを利用して、より大きな単語のセットを見つけました。非常に大きな単語セットを見つけましたが、それらのリストから完璧なパングラムを探し始めたとき、有効な英語の単語ではない低品質の単語で汚染されすぎていることがわかりました。何度も繰り返した後でも、リストを整理して、合理的または管理しやすいパングラムを見つけることができませんでした。特定の長さの単語のホワイトリストを作成してクリーンアップしようとしましたが、リストの品質は依然として非常に低かったです。
最後に、何度も繰り返した後、北米のトライアルメンバーシップを購入するために15ドルを支払いました。 Scrabble®PlayersAssociationは、いくつかの論争の原因となっている所有権と著作権で保護されたOWL3へのアクセスを私に与えてくれました。それでも、1文字の単語「a」や「I」など、英語の既知の単語をいくつか追加する必要がありました。
適切な単語リストを用意して、生成するアルゴリズムを実装しました。そのリストのすべての単語セットで、それぞれに英語のアルファベットの各文字が1つずつ含まれています。アルゴリズムについては、以下の「アルゴリズム」セクションで詳しく説明します。
ステップ2：単語の袋から英語の文章を作成する
単語のセットを指定して、提供されたすべての単語で有効な英語の文が可能ですが、それは重要な問題ですが、他のほとんどの自然言語処理（NLP）の問題よりも簡単です。
不適格な文を取り除くための便利なヒューリスティックがあります。これらのヒューリスティックに従って、残りの単語から有効な英語の文を作成することができました。文章はしばしば無意味でしたが、それでも有効でした。私が使用したヒューリスティックは次のとおりです。
- 少なくとも1つの動詞が必要です。
- 結合または結合がない限り、動詞よりも名詞が1つだけ多くなります。どちらも非常にまれな前置詞です。
- 形容詞がある場合は、名詞も必要です。
ヒューリスティックは、暗黙の可能性があるため、部分的に機能します。主語（完璧でもパングラムでもありませんが、「静かに動き、柔らかく話す」とは、動詞が2つあり、名詞がなく、主語が「あなた」であることを意味します）。
おそらく完璧なパングラムに参加するのは小さいので、個々の単語にその適格な音声部分を手動でタグ付けして、単語のセットがこれら3つの単純なヒューリスティックに従っているかどうかを確認するのは簡単です。生成される文の品質が好きかどうかは好みの問題です。
アルゴリズム
このセクションは少し技術的ですが、それでも簡単に理解できることを願っています。 「結果&学習」セクションに進んでください。
高レベルの戦略
目標は、次の可能なすべてのセットを作成することです。英語のアルファベットに「完全に」及ぶ単語のリストからの単語。
- 単語のリストをクリーンアップして、検索スペースを大幅に削減します。 「文字」など、文字が繰り返されている単語を削除します。
- ビットマスクを使用して単語を効率的に表現し、元の単語セットにマッピングし直します。
- 考えられるすべての状態を検索し、それぞれがビットマスクのリストを繰り返し繰り返すことにより、可能な文字の組み合わせを表します。動的プログラミングによりパフォーマンスが劇的に向上します。
- 完全なパングラム状態から矢印（有向エッジ）を描画します。英字、それを構成する中間州へ。中間州でこれを繰り返して、完全なパングラムとなる可能性のある単語のセットを再構築できるデータ構造を作成します。これはバックトラッキングと呼ばれます。
- 出力発見された単語のセットは、木として完璧なパングラムである可能性があります。
リストのクリーンアップ、別名正規化
最初のステップは、元の単語リストをクリーンアップして検索スペースを減らし、出力品質を向上させることです。
- 単語の周囲の空白をすべて削除します。小文字のみに変換します
- 単語に英語のアルファベットの文字のみが含まれていることを確認します。単純な正規表現フィルターを使用しました：
/^+$/ - 他のリストに対してフィルターします。ブラックリスト;単語がブラックリストに含まれている場合は、その単語をスキップします
- 繰り返し文字が含まれるすべての単語を削除します
これにより、検索スペースが200,000〜370,000単語のリストから大幅に短縮されました。はるかに小さい35,000〜65,000ワード。
ビットマスクの使用
ビットマスクは状態の整数表現です。ビットマスクにはいくつかの利点があります。
- ビットマスクはこの問題をよく表しています。文字の順序は重要ではないため、単語のすべての組み合わせは、0と1の26桁の長さのシリーズとして表すことができ、各桁は、組み合わせに文字が存在するかどうかを表します。例えば。単語のセットに文字「e」が含まれている場合、5桁目は1になり、そうでない場合は0になります。
- ビットマスクは効率的です：検索スペースが一定であるため、ビットマスクは効率的なストレージを提供します。文字の可能なすべての組み合わせの表現さらに、ビット単位の操作は高速です。2つのビットマスクを組み合わせてより大きなビットマスクを生成できるかどうかをテストするには、2つのマスクのビット単位のANDが0に等しいかどうかを確認します。どちらも非常に優れています。高速操作。
したがって、各単語をビットマスクに変換します。ビットマスクは整数で表すことができます。たとえば、単語「cab」は111のビットマスクにマップされます。は10進数の7です。単語「be」は10010にマッピングされます。これは10進数の18などです。可能な最大のビットマスクは、アルファベットのすべての文字を含むもの、可能な完全なパングラム状態、11111111111111111111111111、これは、10進数の67、108、863、または2²⁶-1です。これは、標準の符号付き32ビット整数にうまく適合します。 to2³¹-1。
単一の単語のアナグラムが同じビットマスクにマップされるため、ビットマスクを使用するとスペースがさらに圧縮されます。 「窯」と「リンク」の両方が、10進数11520であるマスク10110100000000にマップされます。これにより、35,000〜65,000ワードの検索スペースが25,000〜45,000ビットマスクにさらに削減されます。
ビットマスクのマッピングを保持して、それらが派生した単語のセットに戻します。これは、単語のセットを出力するときに役立ちます。
動的計画法で完璧なパングラムを検索する
アルゴリズムのコアはかなり単純です：
可能な状態（既存の単語の有効な組み合わせで構成される）が与えられた場合、最初の単語リストのすべてのマスクを試して、新しい有効な状態を作成できるかどうかを確認します（状態とマスクは0に等しく、これは重複する文字がないことを意味します）。すべての1をマージするビットごとのOR演算を使用して、新しい状態を作成します。発見された新しい状態ごとに、未探索の状態がなくなるまで繰り返します。これが終わりに達した場合、それはアルゴリズムが少なくとも1つの可能な完全なパングラム単語セットを見つけたことを意味します。すべての可能な状態を列挙できる最初の可能な状態は、空の状態または0であり、アルファベットの文字は含まれていません。したがって、そこから始めて、どの状態が可能かを再帰的に発見します。
効率が大幅に向上するのは、断続的な状態に到達する方法がたくさんあり、状態の作業がその方法に基づいて変化しないことに気付くことです。到達しました。したがって、状態が再検討されたときに作業を繰り返す代わりに、各状態の結果を保存します。この手法は動的計画法と呼ばれ、複雑な組み合わせ問題を線形計画法に変えます。断続的な状態を保存するプロセスはメモ化と呼ばれます。
したがって、0から67,108,863までのサイズ2²⁶の配列を作成します。各インデックスは、前に説明したようにビットマスクの状態を表します。配列の各インデックスの値は、状態についてわかっていることを表します。 0は、状態が変更されていないか、到達できないことを意味します。 1は、状態が可能な完全なパングラム状態に到達する方法を見つけたことを意味します。 -1は、状態が最後に到達する方法を見つけられなかったことを意味します。
以下の擬似コード：
間奏：複雑さと実用的なランタイム分析
あります一連の26ビットの2²⁶可能なビットマスク。各状態はメモ化のために1回だけ処理されるため、このアルゴリズムの実行時間はO（n 2 ^ d）です。ここで、dはアルファベットのサイズ26です。変数nは単語数を表しませんが、ビットマスクの数。 67,108,863と約45,000のビットマスクを使用すると、これは3兆のオーダーになり、私のMacBookProは約45分で処理できます。最新のコンピューターで扱いやすい。また、再帰的な呼び出しスタックが26より深くなることはない（15より深くなることはない）ため、その次元からも非常に管理しやすいことにも注意してください。
ビットマスクアプローチの利点の1つは、 2²⁶状態のみが、すべての状態をメモリに格納できることです。状態ごとに3つの値（-1、0、1）しかないため、これを1バイトに格納できます。状態ごとに1バイトの場合、2²⁶状態は約67メガバイトになります。これも非常に扱いやすいです。
ただし、アルファベットが増えると、検索スペースが指数関数的に増加し、実行時間も増加します。非常に早く手に負えなくなる問題。大きなアルファベットの完璧なパングラムへのアプローチに関する簡単な説明は、以下の「大きなアルファベットのある言語」セクションにあります。
有向非周期的グラフ（DAG）の動的な構築
これで、ビットマスクの状態を入力しました。解決策を取得する時間です。
可能な完全なパングラムのセットを作成した単語のセットを見つけるには、最終状態の構成に不可欠な中間状態を導出する必要があります。次に、フォローアップの質問は、他のどの中間状態がそれらの中間状態を構成したかということであり、残りの唯一のものが単語に直接マップされる状態になるまで続きます。このプロセスはバックトラッキングと呼ばれます。
維持する状態間の関係を追跡し、目標はDiを作成することです有向非巡回グラフ（DAG）。これは、どの中間状態が任意の状態を構成するかを維持します。 DAGは、特に非周期的な性質があるため、出力を取得するために簡単にトラバースできます。構築するには、可能な完全なパングラム状態から開始し、それを構成する中間状態を指す有向エッジ（矢印）を作成します。中間状態でこのプロセスを繰り返すと、DAGが生成されます。矢印は常に小さい値の状態を指しているため、サイクルは発生しません。
検索ステップで発見された関係を再構築する（数兆の可能な状態の組み合わせを再度トラバースする）代わりに、動的計画法フェーズでDAGを構築する方が効率的です。解決方法の内部で、新しく構築された状態が可能な完全なパングラム状態に到達できる場合、元の状態がその補数よりも小さい場合にのみ、新しく構築された状態から元の状態への有向エッジを格納します（エッジの重複を減らすため）。
労働の成果をツリー形式で印刷してください！
結果の単語セットを表示するための最も簡単な形式は、ルートノードを完全なパングラム状態としてツリーとしてリストすることです。上から構築されたDAGを考えると、それをアンパックする最良の方法は、ツリーがDAGよりも桁違いに大きいため、メモリ内ではなく各ステップで各状態をディスクに書き込むことです。
この形式の拡張の改善点は、単語の可能な組み合わせが1つしかない状態を要約することです。単語のマスクであり、それを構成するサブステートがない状態は、簡単に要約できます。状態は、そのサブ状態とその複合を要約でき、それ自体とその子から派生したすべてのマスクに重複するビット/文字がない場合に要約できます。要約されたDAGを印刷すると、出力ツリーが短縮および簡略化されるため、結果の出力ツリーの可読性が向上します。
要約は2つの状態の小さい方にのみ依存するため、配列を初期状態の0から上に繰り返します。上記のルールを使用して要約ルールを管理すると、これを線形時間で完了することができます。
作成されたパングラムツリー！
自由に完璧なパングラムツリーをトラバースして、次のことを確認してください。面白い文章を見つけることができます！
完璧なパングラムはたくさんあります
完璧なパングラムの数に驚きました。たくさんあります！それらをつなぎ合わせるための最良の戦略は、複雑な自然言語プロセッサを必要としません。候補単語が名詞または動詞適格としてラベル付けされたら、単語のバッグには、少なくとも1つの名詞、1つの動詞、および名詞と動詞の適切な比率が含まれている必要があります。
データ品質は難しい問題です
アルゴリズムセクションには2日かかりましたが、データ品質の問題には2週間かかりました。 Googleのシニアスタッフエンジニアである友人にこの発見について話したとき、彼は驚かず、データ品質の問題はエンジニアリングで最も難しい問題のいくつかであるとコメントしました。教訓。
完璧なパングラムのルール
完璧なパングラムと見なされるものについては、さまざまなニュアンスがあります。感動詞（hm、phtなど）を使用せずにパングラムを検索したかったのですが、略語、頭字語、短縮形、頭字語、孤立した文字、固有名詞、ローマ数字など、他にも一般的な制限があります。 Qophのように、浮気をしていると感じた文字の名前の単語もあります。
これらの制約のいくつかが緩和されているため、「完璧な」パングラムがたくさんあります。おそらく数兆のオーダーです。 。頭字語やイニシャリズムがたくさんあります。
アスタリスク
英語のすべての完璧なパングラムの定義が明確に定義されていないため、アスタリスクが設定されています。ニュアンスがあります。完璧な英語のパングラムで何が許されるべきかということに関して。いくつかの単語が英語の単語でさえあるかどうかについても多くの論争があります。これらのニュアンスを考えると、完璧なパングラムをすべて見つけたとは言い難いです。私はかなり自信を持って2つの主張をすることができます：
- 類似またはより小さな文字セットを持つ英語および他の言語の完璧なパングラムをすべて作成する方法を見つけました。
- I公式のScrabbleトーナメント辞書を使用して完璧なパングラムを形成できる可能性のあるすべての単語セットを列挙しましたy、OWL3。
この投稿で説明されている手法を使用して、独自の完璧なパングラムを自由に作成してください！
完璧なパングラムのウェールズ語とアラビア語のルーツの単語への依存
ウェールズ語とアラビア語から派生した単語は、完全な英語のパングラムが存在するために非常に重要でした（完全なパングラムの制約が緩和されない限り）。完全なパングラムに関する厳格なルールを持つOWL3単語リストを使用すると、両方ともウェールズ語である「cwm（s）」または「crwth（s）」という単語を含まない完全なパングラムはありません。国際的なスクラブルでは、アラビア語から派生した単語「waqf（s）」は、「cwm（s）」や「crwth（s）」に頼らずに完璧なパングラムを作成できる有効な単語です。
ワークストリームの効率
このプロジェクトでは、タスクの並列化をより効率的にすることが重要でした。フルランは、Unix辞書の場合は25分、非常に大きな辞書の場合は1時間近くかかります。 30分間のウィンドウでコンテキストの切り替えに最初の問題が発生しましたが、生産性を向上させるために進むにつれて、状況が改善されました。
拡張/一般化— Anagram Finder
完璧なパングラム検索は、文字列「abcdefghijklmnopqrstuvwxyz」のアナグラムファインダーにも相当します。一般的なアナグラムファインダーを作成する場合はどうなりますか？
状態の表現とチェックの管理ルールがあれば、同じ手法を使用できます。単語の組み合わせの有効性が更新されます。状態を整数として管理する代わりに、関連する文字のマップとして状態を追跡する方が簡単です。組み合わせが有効かどうかを確認するには、2つのマップの組み合わせがアナグラムの各文字に必要な文字数。状態スペースが扱いやすいことを確認してください。文字が多すぎると、検索スペースが非常に大きくなる可能性があります。また、単語を繰り返すことはできますか？内部でこれらのルールを定義してください。あなたのダイナミックプログラミング解決策。
大きなアルファベットの言語
このアプローチと解決策は、単語セットのサイズでは線形ですが、アルファベットのサイズでは指数関数的です。このアプローチは、46の音節文字を持つ現代の日本語など、より大きな文字セットでは機能しない可能性があります。 2⁴⁶は70,368,744,177,664です。英語の検索スペースである2²⁶= 67,108,864の100万倍以上です。
このアプローチが日本人に有効かどうかは完全には明らかではありません。日本語のエントロピーが十分に低い場合（可能）、このアプローチは実行可能です。サイズ2⁴⁶の配列を初期化する代わりに、状態はマップで追跡され続けます。さらに、日本語の構造を利用することができます。たとえば、かなを（wo）は、ほとんど専ら事後分詞として使用され、検索から除外できるため、検索スペースが削減されます。
カンボジア語のクメール語は、アルファベットが最大で74です。もう1つの可能な次のステップは、アルファベットサイズが指数関数的でないソリューションを探索することです。
インスピレーション
オーブリーデグレイの進歩により、平面の色数を見つけることに触発されました。少なくとも5。これは基本的な計算方法によって達成された重要な進歩です。
言うまでもなく、完璧なパングラムを見つけることは、平面の色数の下限を改善することにはなりません。
これにより、手作業で扱いにくい問題を解決するための簡単な計算方法を備えた、ぶら下がっている果物の問題がたくさんあると思います。これらの問題のいくつかを見つけて解決するようにあなたに挑戦します。何か見つけたら教えてください！
ありがとう
私と一緒に校正と妨害を手伝ってくれた非常に優秀な友人、特にアンナ・ゼン、キャサリンにとても感謝していますGao、Danny Wasserman、George Washington、Nick Wu！