python - スペース/結合された単語のないテキストから最も可能性の高い単語を検出する

Question

結合された文字列から単語を検出して分割するにはどうすればよいですか？

例：

"cdimage" -> ["cd", "image"]
"filesaveas" -> ["file", "save", "as"]

Answer 1

これが動的プログラミングソリューションです（メモ化された関数として実装されています）。頻度のある単語の辞書が与えられると、全体的に最も可能性の高いフレーズを与える位置で入力テキストが分割されます。実際の単語リストを見つける必要がありますが、簡単なテストのためにいくつかの構成された頻度を含めました。

WORD_FREQUENCIES = {
    'file': 0.00123,
    'files': 0.00124,
    'save': 0.002,
    'ave': 0.00001,
    'as': 0.00555
}

def split_text(text, word_frequencies, cache):
    if text in cache:
        return cache[text]
    if not text:
        return 1, []
    best_freq, best_split = 0, []
    for i in xrange(1, len(text) + 1):
        word, remainder = text[:i], text[i:]
        freq = word_frequencies.get(word, None)
        if freq:
            remainder_freq, remainder = split_text(
                    remainder, word_frequencies, cache)
            freq *= remainder_freq
            if freq > best_freq:
                best_freq = freq
                best_split = [word] + remainder
    cache[text] = (best_freq, best_split)
    return cache[text]

print split_text('filesaveas', WORD_FREQUENCIES, {})

--> (1.3653e-08, ['file', 'save', 'as'])

Answer 2

そのためのライブラリは知りませんが、基本的な機能を実装するのは難しいことではありません。

1. UNIXのような単語リストを取得しますwords。
2. 単語リストの内容をトライに詰め込みます。
3. 分割したい文字列を取り、トライ内のパスをたどります。有効な単語に到達するたびに、到達した文字列のポイントから開始して単語を検索する新しいブランチを作成します。現在のブランチを終了したら、深さ優先探索のように、作成したブランチに戻ります。
4. ヒューリスティックを使用して、または自然言語パーサーを使用して、結果のリストを手動で明確にします。

例：

1. 単語： "filesaveasstring"
2. 最初の有効な単語は「ファイル」です。「saveas」を一致させてみてください。最初の有効な単語は「保存」です。「asstring」を一致させてみてください。最初の有効な単語は「as」です。「文字列」を一致させてみてください。最初の有効な単語は「文字列」です。最後まで一致しました。[ファイルを文字列として保存]を結果リストに追加します。
3. 一致する「文字列」に戻る-他の可能性はありません。「asstring」に戻り​​ます。最初に訪れていない有効な単語は「お尻」です。「tring」を一致させてみてください。一致する可能性はありません。「asstring」に戻り​​ます。一致する可能性はありません。「filesaveasstring」に戻り​​ます。
4. 最初の未訪問の一致は「ファイル」です。「aveasstring」と一致させてください。最初の一致は「ave」です。「asstring」（手順2/3と同じ結果）を一致させて、結果リストに[files ave as string]を追加し、最初に戻ってみてください。
5. 「filesaveasstring」と一致させてみてください。未訪問の試合はありません。終わり。
6. ヒューリスティックまたは自然言語パーサーを使用して、[[ファイルを文字列として保存][ファイルを文字列として保存]]から最も可能性の高いものを選択します。

Answer 3

これを行うライブラリはわかりませんが、単語のリストがあれば書くのはそれほど難しくありません。

wordList = file('words.txt','r').read().split()
words = set( s.lower() for s in wordList )

def splitString(s):
    found = []

    def rec(stringLeft, wordsSoFar):
        if not stringLeft:
            found.append(wordsSoFar)
        for pos in xrange(1, len(stringLeft)+1):
            if stringLeft[:pos] in words:
                rec(stringLeft[pos:], wordsSoFar + [stringLeft[:pos]])

    rec(s.lower(), [])
    return found

これにより、文字列を指定された単語に分割するためのすべての可能な方法が返されます。

例：

>>> splitString('filesaveas')
[['file', 'save', 'as'], ['files', 'ave', 'as']]

Answer 4

この例を見ることができます：しかし、それはscalaで書かれています。これにより、文の間にスペースがない場合に、必要なものを分割できます。

Nonspaced-Sentence-Tokenizer

Answer 5

この質問がPython用にマークされていることは知っていますが、JavaScriptの実装が必要でした。以前の回答から離れて、コードを共有すると思いました。きちんと動作するようです。

function findWords(input){
    input = input.toLowerCase().replace(/\s/g, ""); //Strip whitespace

    var index = 0;
    var validWords = [];
    for (var len = input.length; len > 0; len--){ //Go backwards as to favor longer words
        var testWord = input.substr(index, len);
        var dictIndex = _dictionary.indexOf(testWord.replace(/[^a-z\']/g, "")); //Remove non-letters
        if (dictIndex != -1){
            validWords.push(testWord);
            if (len == input.length){
                break; //We are complete
            }
            var nextWords = findWords(input.substr(len, input.length - len)); //Recurse
            if (!nextWords.words.length){ //No further valid words
                validWords.pop();
            }
            validWords = validWords.concat(nextWords.words);
            if (nextWords.complete === true){
                break; //Cascade complete
            }
        }
    }
    return {
        complete:len > 0, //We broke which indicates completion
        words:validWords
    };
}

注：「_ dictionary」は、頻度でソートされた単語の配列であると想定されています。ProjectGutenbergのワードリストを使用しています。