単語とスペースのない文字列がある場合、それらの単語を含む辞書/リストがあるとすれば、どのようにそれらの単語を解析する必要がありますか?
たとえば、文字列が「thisisastringwithwords」の場合、辞書を使用して「this is a string with words」という出力を作成するにはどうすればよいでしょうか?
データ構造Triesを使用すると役立つと聞きましたが、誰かが疑似コードを手伝ってくれるとしたら? たとえば、辞書をトライ構造にインデックス付けしてから、各文字をトライに沿って追跡できるのではないかと考えていました。問題は、（疑似）コードでこれを行う方法に慣れていないことです。
テキストが辞書の単語で始まっているかどうかを繰り返しチェックする明白な解決策ではなく、効率的な解決策が必要だと思います。
辞書が十分に小さければ、標準のKMPアルゴリズムを変更してみることができると思います。基本的に、辞書上に有限状態マシンを構築します。このマシンは、テキストを1文字ずつ消費し、構築された単語を生成します。
編集：私は試みを再発明していたようでした。
私はすでに似たようなことをしました。簡単な辞書は使えません。結果はぐちゃぐちゃになります。これを一度だけ行う必要があるか、プログラム全体で行う必要があるかによって異なります。
私の解決策は次のとおりでした：
次に、「可能性の表」を作成する必要があります。多くの単語は 100% に収まる可能性がありますが、間違っています。言葉が長ければ長いほど、この言葉が正しいと確信できます。
CPU を集中的に使用しますが、結果は正確に機能します。たとえば、10,000 語の小さな辞書を使用していて、そのうち 3,000 語が 8 文字の長さである場合、最初に bigString を 3,000 語すべてと比較する必要があり、結果が見つかった場合にのみ、次に進むことができます。次の言葉。bigString に 200 文字ある場合、(2000 文字 / 平均 8 文字) = 250 回の完全なループが最小で必要です。
私にとっては、スペルミスのある単語の小さな検証も比較に加えました.
手順例（コピペ不可）
Dim bigString As String = "helloworld.thisisastackoverflowtest!"
Dim dictionary As New List(Of String) 'contains the original words. lets make it case insentitive
dictionary.Add("Hello")
dictionary.Add("World")
dictionary.Add("this")
dictionary.Add("is")
dictionary.Add("a")
dictionary.Add("stack")
dictionary.Add("over")
dictionary.Add("flow")
dictionary.Add("stackoverflow")
dictionary.Add("test")
dictionary.Add("!")
For Each word As String In dictionary
If word.Length < 1 Then dictionary.Remove(word) 'remove short words (will not work with for each in real)
word = word.ToLower 'make it case insentitive
Next
Dim ResultComparer As New Dictionary(Of String, Double) 'String is the dictionary word. Double is a value as percent for a own function to weight result
Dim i As Integer = 0 'start at the beginning
Dim Found As Boolean = False
Do
For Each word In dictionary
If bigString.IndexOf(word, i) > 0 Then
ResultComparer.Add(word, MyWeightOfWord) 'add the word if found, long words are better and will increase the weight value
Found = True
End If
Next
If Found = True Then
i += ResultComparer(BestWordWithBestWeight).Length
Else
i += 1
End If
Loop
辞書にそのフレーズのすべての単語があることが確実な場合は、そのアルゴを使用できます。
String phrase = "thisisastringwithwords";
String fullPhrase = "";
Set<String> myDictionary;
do {
foreach(item in myDictionary){
if(phrase.startsWith(item){
fullPhrase += item + " ";
phrase.remove(item);
break;
}
}
} while(phrase.length != 0);
いくつかの項目が同じように始まるなど、非常に多くの複雑さがあります。そのため、コードは、ツリー検索やBSTなどを使用するように変更されます。
不可能な作業のようだと言いました。しかし、あなたはこの関連するSOの質問を見ることができます-それはあなたを助けるかもしれません。
わかりました、これで手を波打つ試みをします。問題に最適な（っぽい）データ構造は、（トライを言ったように）辞書の単語で構成されています。トライはDFAとして最もよく視覚化されます。これは、新しいキャラクターごとに1つの状態から次の状態に移動する優れたステートマシンです。これはコードで行うのは本当に簡単です。このためのJava（ish）スタイルのクラスは次のようになります。
Class State
{
String matchedWord;
Map<char,State> mapChildren;
}
これ以降、トライの作成は簡単です。これは、各ノードに複数の子を持つルートツリー構造を持つようなものです。各子供は1つのキャラクタートランジションで訪問されます。HashMapある種の構造を使用すると、次のStateマッピングへの文字を検索するための時間が短縮されます。あるいは、アルファベットが26文字しかない場合は、afixed size array of 26でもうまくいきます。
さて、それがすべて理にかなっていると仮定すると、あなたはトライを持っていますが、あなたの問題はまだ完全には解決されていません。これは、正規表現エンジンが行うようなことを開始し、トライを歩き、辞書内の単語全体に一致する状態を追跡し（構造matchedWord内で私が求めていたものですState）、バックトラッキングロジックを使用してジャンプする場所です。現在のトレイルが行き止まりに達した場合の以前の一致状態。私はその一般的なことを知っていますが、トライの構造を考えると、残りはかなり簡単です。
単語の辞書があり、迅速な実装が必要な場合、辞書検索が O(1) であると仮定すると、これは O(n^2) 時間で動的プログラミングを使用して効率的に解決できます。以下はいくつかの C# コードです。部分文字列の抽出と辞書検索が改善される可能性があります。
public static String[] StringToWords(String str, HashSet<string> words)
{
//Index of char - length of last valid word
int[] bps = new int[str.Length + 1];
for (int i = 0; i < bps.Length; i++)
bps[i] = -1;
for (int i = 0; i < str.Length; i++)
{
for (int j = i + 1; j <= str.Length ; j++)
{
if (bps[j] == -1)
{
//Destination cell doesn't have valid backpointer yet
//Try with the current substring
String s = str.Substring(i, j - i);
if (words.Contains(s))
bps[j] = i;
}
}
}
//Backtrack to recovery sequence and then reverse
List<String> seg = new List<string>();
for (int bp = str.Length; bps[bp] != -1 ;bp = bps[bp])
seg.Add(str.Substring(bps[bp], bp - bps[bp]));
seg.Reverse();
return seg.ToArray();
}
/usr/share/dict/words の単語リストを使用して hastset を作成し、次のコマンドでテストします
foreach (var s in StringSplitter.StringToWords("thisisastringwithwords", dict))
Console.WriteLine(s);
「単語を含む文字列」という出力が得られます。他の人が指摘しているように、このアルゴリズムは有効なセグメンテーション (存在する場合) を返しますが、これは期待するセグメンテーションではない可能性があります。短い単語が存在すると、セグメンテーションの品質が低下します。2 つの有効なサブセグメンテーションが要素に入った場合、ヒューリスティックを追加して長い単語を優先できる場合があります。
複数のセグメンテーションを生成し、確率的ランキングを適用できる有限状態マシンと言語モデルを使用する、より洗練された方法があります。
これは、単語間にスペースがない中国語のような言語をプログラムで解析しようとするときに発生する正確な問題です。これらの言語で機能する 1 つの方法は、句読点でテキストを分割することから始めることです。これにより、フレーズが得られます。次に、フレーズを繰り返し処理し、辞書で最も長い単語の長さから始まる単語に分割してみます。長さが13文字だとしましょう。フレーズの最初の 13 文字を取り出して、辞書に載っているかどうかを確認してください。もしそうなら、今のところそれを正しい単語と見なして、フレーズを進めて繰り返します。それ以外の場合は、部分文字列を 12 文字に短縮し、次に 11 文字に短縮します。
これは非常にうまく機能しますが、最初に来る単語に誤ってバイアスをかけているため、完全ではありません。このバイアスを取り除き、結果を再確認する 1 つの方法は、フレーズの終わりからプロセスを繰り返すことです。同じ単語区切りが得られれば、おそらくそれは良いと言えます。そうでない場合は、単語セグメントが重複しています。たとえば、サンプル フレーズを最後から解析すると、次のようになる可能性があります (強調のために後方に)
words with string a Isis th
最初は、イシス (エジプトの女神) という言葉が正しいように見えます。ただし、「th」が辞書にない場合は、単語の分割に問題があることがわかります。両方の単語がディクショナリに含まれているため、整列されていないシーケンス「thisis」の前方セグメンテーション結果「this is」を使用して、これを解決します。
この問題のあまり一般的ではない変種は、隣接する単語がどちらの方向にも進む可能性のあるシーケンスを共有する場合です。「アルカンド」（何かを作り上げる）のようなシーケンスがあった場合、それは「アークハンド」または「アーチアンド」のどちらである必要がありますか? 決定する方法は、文法チェッカーを結果に適用することです。とにかく、これはテキスト全体に対して行う必要があります。