ワード分離アルゴリズム

Question

ドメインパーキングページで使用されていると思われるアルゴリズム（つまり、「thecarrotofcuriosity」など）と、より多くの場合は正しく構成ワードに分解されるアルゴリズム好奇心の人参 "）？

Answer 1

普通の園芸品種のUnixシステムで/usr/share/dict/wordsのような辞書の単語リストを取って、元のテキストの最大量をカバーする単語マッチのセットを見つけようと思っています試合。単純な幅優先探索の実装は、明らかに速く実行する必要がないため、おそらくうまく動作します。

Answer 2

私はこれに似たそれを行うこれらのサイトを画像化したい：

1. がターゲット言語
2. のために単語のリストを取得し、「A」のような「役に立たない」の言葉、「」削除.. 。
3. リストを実行し、ドメイン名のストリング
4. は（...、あるいは、最高のAdSenseの定格を持つもの）、残りのリストの最も一般的な単語を取るされている単語のどのチェック

もちろん、これはノンセンスのエキスパートエクスチェンジにつながりますが、それ以外に何が期待されますか？

Answer 3

（免責事項：私は自分で試していないので、単に実験用の食べ物として服用しています。 3グラムはあまりうまく動かないと私の経験からちょうど4グラムが青い空からほとんど取り出されます。かなり大きなテーブルに対処する必要があるにしても、5グラム以上の方がうまくいくかもしれません）。ストリングの終わりをアカウントに取り込まないという意味では単純すぎます。そうでない場合は、おそらくエンディングの修正について考える必要があります。

このアルゴリズムは、分割しようとしている文字列の長さに比例した予測可能な時間内に実行されます。

だから最初に、人間が読めるテキストをたくさん読んでください。テキストのそれぞれについて、それが単一の文字列であると仮定すると、str、次のアルゴリズムを実行します（擬似コードish表記、[]はハッシュテーブルのようなインデックスであり、存在しないインデックスは '0'を返します）。

for(i=0;i<length(s)-5;i++) { 
    // take 4-character substring starting at position i 
    subs2 = substring(str, i, 4); 
    if(has_space(subs2)) { 
    subs = substring(str, i, 5); 
    delete_space(subs); 
    yes_space[subs][position(space, subs2)]++; 
    } else { 
    subs = subs2; 
    no_space[subs]++; 
    } 
} 

これは、指定された4グラムにスペースを挿入する必要があるかどうかを判断するのに役立つテーブルを作成します。その後

、分割するために、あなたの文字列を取る、私はXSTRとしてそれを示し、実行します。

for(i=0;i<length(xstr)-5;i++) { 
    subs = substring(xstr, i, 4); 
    for(j=0;j<4;j++) { 
    do_insert_space_here[i+j] -= no_space[subs]; 
    } 
    for(j=0;j<4;j++) { 
    do_insert_space_here[i+j] += yes_space[subs][j]; 
    } 
} 

その後、あなたは「do_insert_space_here []」配列歩くことができます - 指定した位置にある要素の場合を位置が0より大きい場合は、元の文字列のその位置にスペースを挿入する必要があります。ゼロよりも小さい場合は、そうしないでください。

あなたがそれ（あるいはこの種の何かを）しようとすると、ここで注意をドロップすると、それはあなたの辞書を表す基本的なTrieデータ構造をあなた:-)

Answer 4

スタートのために働く（または動作しません）してください。文字列の文字を繰り返していくうちに、単一のポインタではなくポインタのセットでトライを検索します。セットにはトライのルートが入ります。各文字の場合、セット全体が文字で示されたポインタを介してすぐに進められ、セットされた要素を文字で進めることができない場合は、セットから取り除かれます。可能な単語の終わりに達するたびに、新しいルートトライをセットに追加します（そのセットエレメントに関連付けられている単語のリストを追跡します）。最後に、すべての文字が処理されたら、トライのルートにある単語の任意のリストを返します。複数の場合は、文字列を複数の方法で分割することができます（「セラピスト」、「フォーラム」または「the」、「rapist」、「forum」など） ]）、返されるのは未定義です。

あるいは、アップwacked擬似コードで（頭を使用して、Javaのforeach、括弧で示さタプル、中括弧で示されているセット、cons ::尾、[]は空のリストです）：

List<String> breakUp(String str, Trie root) { 
    Set<(List<String>, Trie)> set = {([], root)}; 
    for (char c : str) { 
     Set<(List<String>, Trie)> newSet = {}; 
     for (List<String> ls, Trie t : set) { 
      Trie tNext = t.follow(c); 
      if (tNext != null) { 
       newSet.add((ls, tNext)); 
       if (tNext.isWord()) { 
        newSet.add((t.follow(c).getWord() :: ls, root)); 
       } 
      } 
     } 
     set = newSet; 
    } 
    for (List<String> ls, Trie t : set) { 
     if (t == root) return ls; 
    } 
    return null; 
} 

は、私を知ってみましょう私が明確にする必要があるか何かを逃した...