14

Mad Gabスタイルのフレーズを提案するアルゴリズムを作成しようとしています。

入力はフレーズのセットです。また、可能であれば使用したいキーワードのセットもあります。現在、私の解決策は単純にブルートフォースです:

  • フレーズをループする (文字ごと)
    • キーワードが見つかった場合
      • キーワードと分岐を格納 (再帰)
    • 文字数を増やす

ただし、私が直面している問題は次のとおりです。

  • 複合キーワードの説明。たとえば、「キャッチ」は「キャッチ」、「猫」+「チーズ」のようになります
  • 「the」、「and」、「one」、「two」、「three」などの文字通りの用語を許可します。
  • キーワードではない用語を提案する方法。つまり、キーワードやリテラルが見つからない場合は、システム ディクショナリのようなものに頼ります。
  • フレーズ セグメントをスキップします。現在、1回のパススルーのみです。しかし、フレーズが一致しないもので始まり、数文字後に一致が含まれる場合を考えてみましょう。

私は PHP と MySQL に最も精通しています。ただし、より優れたソリューションが提供される場合は、別のテクノロジを受け入れます。

また、追加の提案にも興味があります。特に、 の 2 番目のパラメーターを使用してより難しい提案metaphone()を行う方法。

4

2 に答える 2

6

おそらく、句バンクの音節分割アルゴリズムから始めます。子供たちに音節を分割することを教える簡単なリソースを使用して、大まかな分割方法を作成することもできます。

http://www.ewsdonline.org/education/components/scrapbook/default.php?sectiondetailid=7584

より技術的で完全に正確な方法が必要な場合は、博士号がありました。それを行う方法についての論文:

http://www.tug.org/docs/liang/

次に、自分でロールするものまたは metaphone() を使用して、各音節を音声表現に変換します。母音の規則を説明している同様のサイトを使用できます。これらは一般化にすぎません。独自にロールする場合は、子音とは別に母音を処理します。Metaphone は子音のみを使用します。これは問題ありませんが、母音も考慮した場合ほどクールではありません。

母音: http://www.eslgold.com/pronunciation/english_vowel_sounds.html 子音: http://usefulenglish.ru/phonetics/english-consonant-sounds

次に、単語バンク用の英単語の辞書があります。MySQL テーブルに貼り付けることができるオープンソースの辞書が多数あります。

最初の音節から始めて、soundex テストに一致する単語を辞書でランダムに探します。見つからない場合 (これは通常、1 つの音節の単語のみを検索します)、追加の音節を追加して、再度検索します。

例:

「論理的帰結」

A. 音節分割

「論理的帰結」

B. 適用された母音

「lah gee cahl con see quince」

C.子音の適用

「lah jee kahl kon see quinse」

D. サウンドテキスト テスト (1 音節の soundex - 推測するのは明らかに簡単ですが、概念を証明します)

「ロージーコールコンシークインツ」

Soundex strcmp は数値を返します。したがって、必要に応じて、単語バンク内のすべてのサウンドの値を事前に取得できます。その後、すぐに strcmp を実行できます。

Soundex MySQL 比較の例は次のとおりです。

select strcmp(soundex('lah'), soundex('law'));

大規模なデータベースからランダムな結果が必要で、辞書テーブルのフィールドに既に soundex 値を取得している場合は、PHP soundex テストよりも MySQL soundex を使用する方が簡単だと思います。

私の提案は非効率的かもしれませんが、最適化は別の問題です。

アップデート:

私の解決策が 1 音節の単語しか生成しないことを意味するつもりはありませんでした。例として 1 つの音節を使用しましたが、2 つの音節を一緒にすると、複数の音節の一致が得られます。実際、すべての音節を一緒に詰め込み、mysql で soundex を実行することから始めることもできます。あなたが答えを見つけたら、素晴らしいです。ただし、可能な限り最長の一致が得られるまで、音節をロールオフできます。次に、フレーズの終わりが残っているので、それらをまとめて試合を行うことができます。それが他の貢献者からの以下のソリューションの本質だと思いますが、スペースなしですべての文字を一緒に詰め込まないようにする必要があると思います. 英語では、そのように情報を失うことになります。「th」の音で始まるフレーズを考えてみましょう。フレーズを詰め込むと、どの「th」が失われますか 音が必要です。「テルミン」(楽器)は、「あれ、男」とは違う「目」の音を持っています。

于 2012-03-28T01:53:30.707 に答える
3

Jonathan Barlowのソリューションとは異なる方法で、ランダム性、堅牢性、およびスケーラブルな難易度で、求めるプロパティを提供するO(n 2 )アルゴリズムをお勧めします。このアルゴリズムの複雑さは、一定時間で、または検索のモダリティを最適化することでさらに改善できますが、入力フレーズのサイズは小さいことが保証されているため、それほど大きな問題にはなりません。

  1. オックスフォード英語辞典のすべての既知の単語のハッシュテーブルと、値ごとの単語リストのマップを作成しsoundex()ます。これは、現在使用されているものが実際にはそれほど多くないことに気付くまで、最初は手に負えないように聞こえます。まともな一方向ハッシュアルゴリズムを想定すると、これには数メガバイト、トップスが必要です。

  2. 入力フレーズ内の単語は、単語の同一性がまったくない単一の圧縮された文字列と見なし、空白とすべての句読点を破棄します。これから、1の長さから始まり、結合されたフレーズの全長から1を引いた長さまで、すべての文字の長さのスペースを歩きます。このウォークによって生成された文字列ごとに、OEDに対してハッシュルックアップを実行します。辞書にある単語が見つかったら、その単語と位置をメモリ内のリストの最後に追加します。

    (このパスは常にsum(n)時間がかかります。これは定義上0.5n(n+1)です。したがって、O(n 2)です。その空間の複雑さは最悪の場合のO(n 2)ですが、実際には、完全に接続された用語のセットはほとんどありません。 )。

  3. 難易度スライダーが登場します。作成されたリストから、見つかった用語の最初のN%を切り取ります。ここで、Nは難易度です。ここでの原則は、小さい単語は誰かが語彙的に処理するのが簡単であるのに対し、長い単語は発音して区別するのが難しいということです。

  4. フレーズの元の長さに一致する配列を作成し(スペースと句読点なし)、検出された単語のリストをシャッフルします。次に、シャッフルされたリストを調べます。要素ごとに、配列内のすべてのスロットが元の位置でその単語に対して空いているかどうかを確認します。そうである場合は、単語とその位置を保持し、配列で使用されているスロットにマークを付けます。そうでない場合は、リストがなくなるまで次の単語に繰り返します。*

  5. 最終的な出力配列から、スペース内の未使用の文字のパーティションリストを作成し、文字の各バッグを独自のフレーズとして扱います。このリストでは、ここmetaphone()にスケッチされているとおりに音節検出を実行し、2つ以上の音節を一緒にグロミングする可能性のパーセンテージで結果を渡します。次に、4。からの出力辞書単語のバッグに対して、実行soundex()し、単語のマップされた比較可能soundexな値のリストからランダムな単語を引き出します。soundex()リストのバッキングマップに従ってそれ自体にしかできないすべての単語に対して、パーティショニングとを実行しmetaphone()ます。最後に、位置で並べ替えて結果の2つのリストをつなぎ合わせ、結果を印刷します。

これは、必要なすべてのプロパティであると私が信じているランダムアルゴリズムですが、それでも私の頭の中では大雑把です。


 *追加のクレジット:文字または音節ごとに、システムで許可されるオーバーラップを決定します。これにより、受け入れられる出力フレーズの範囲がさらに広がり、難易度がはるかに高くなります。

于 2012-03-28T04:50:41.507 に答える