Twitterからのデータを分析するコンテキストでは、ハッシュタグを処理する問題が発生しました。 ハッシュタグを取得して、個別の単語に分割する必要がありました（#habratopic => habra topic）。 タスクは原始的なように見えましたが、私はそれを過小評価していたことがわかりました。 必要なものが見つかるまで、いくつかのアルゴリズムを実行する必要がありました。
この記事は、使用されている各アルゴリズムの長所と短所を分析することで、問題を解決する特定の年表と考えることができます。 したがって、このトピックに興味がある場合は、猫をお願いします。
nlpでは、大きなテキストをスペースなしで分割するタスクは非常に一般的であることに注意してください。 これは、ドイツ語の「長い単語」の単語の定義であり、本質的にはいくつかの連結（ geschwindigkeitsbegrenzung- 制限速度 ）、中国語の文章の単語の定義であり、ほとんどスペースを使用しません（ 城市人的心爱宠物 - 都市住民のお気に入りのペット ）など。 中国語の2番目のケースで、最も単純なアルゴリズムが単語ごとに1文字を考慮して十分に機能する場合、ドイツ語ではすべてがはるかに複雑になります。
アルゴリズム1.最小マッチング
行を調べて、一致する最初の単語を見つけます。 この単語を保存し、残りの行に対して手順を繰り返します。 最後の行で一致する単語がない場合、セグメンテーションは見つからないと見なします。
アルゴリズムは非常に高速ですが（必要なだけ）、非常に愚かです。
例： niceday => nice day 。
しかし、 天気の良い日にはセグメンテーションは見つかりません。 niceが見つかった後、アルゴリズムはwe 、次に記事a 、 the 、および単語rが辞書にないことを判別します。
うん 一致する最初の単語の代わりに、最大長の単語を取得できないのはなぜですか？
アルゴリズム2.最大一致または貪欲
最初の場合と同じことを行いますが、常に最大長の単語を選択します。
アルゴリズムは前のアルゴリズムよりも遅くなります。これは、行の最後から最初に最大長の単語を決定する必要があるためです。 非常に長い行を処理する必要がある場合、速度は著しく低下しますが、Twitterからのデータがあるため、この問題に取り組んでいます。 （実際、行全体ではなく、最初のn文字（nは辞書の最大単語長）を選択すると、速度は平均して最初のアルゴリズムと同じになります）。
例： niceweather => nice weather
ただし、 workingrassの場合、セグメンテーションは再度検出されません。 アルゴリズムに一致する最初の単語は機能しますが、機能しません。また、単語grassの最初の文字を吸収します。
たぶん、何らかの方法で両方のアルゴリズムを組み合わせる必要がありますか？ しかし、文字列niceweatherwhenworkingrassについてはどうでしょうか？ 一般的に、彼らは総当たりした。
アルゴリズム3.ブルートフォース
通常の再帰関数によって文字列を単語に分割するすべての可能なバリアントを生成します。 そのようなオプションは2 ^（N-1）になります。Nは文字列のサイズです。 次に、辞書から部分文字列を含まないオプションを選別します。 結果のオプションは正しいものになります。 アルゴリズムの主な問題は速度です。
やめて！ そして、なぜすべてを生成し、必要なものをすぐに生成できるなら、それをフィルタリングします。
アルゴリズム4.巧妙なブルートフォース
辞書の単語に既に一致したときに再帰呼び出しが発生するように、再帰関数を変更します。 この場合、目的のセグメンテーションがすぐに生成されます。 アルゴリズムは非常に高速で、望ましい結果が得られ、一般に問題は解決したと思いました。
残念ながら、私はあいまいさを見失っています。 実際には、行のセグメンテーションは一意ではなく、同等のパーティションが多数ある場合があります。
例： expertexchange =>（ 専門家の性転換 、 専門家の交換 ）
新しいサブタスクが登場しました。「正しい」セグメンテーションを選択する方法は？
選択肢を最初に、ランダムに、最後に、より多くの単語が存在するもの、より少ない単語が存在するもの、結果がそうであるものを、軽度に、あまりそうではないものとして、調べました。 何らかのスマートなアルゴリズムが必要でした。 私はそれを理解できます
dwarfstealorcoreは、「ドワーフが鉱石やコアを盗む」のではなく、「オークから鉱石を盗む」可能性が高いため、機械が理解する必要があります。 ここで、機械学習アルゴリズムが助けになりました。
アルゴリズム5.あいまいさを解決する巧妙なブルートフォース（ユニグラムモデル）
あいまいさを解決するプログラムを教えるために、モデルを作成するための大きなテキストファイル（トレインセット）をフィードします。 この場合、 ユニグラムモデルは、テキスト内の各単語の使用頻度です。 次に、セグメンテーションの各候補について、候補内の各単語の確率の積として確率を考慮します。 より可能性の高い人は、彼が勝ちました。 すべてがシンプルです。
例： input => in put
意外と？ 単にテキストinには単語inと単語putが含まれているだけで、単語の入力は 1回だけです。 ユニグラムモデルは、単語間の最も原始的な接続についても何も知りません（英語のスピーチの場合、入力された単語の組み合わせはほとんどありません）。
アルゴリズム6.あいまいさを解決する巧妙なブルートフォース（バイグラムモデル）
それでも同じように、バイグラム言語モデルを構築しています。 これは、単語の頻度ではなく、連続するすべての単語のペアの頻度を考慮することを意味します。 たとえば、「 キエフはウクライナの首都です 」という文は 5つのバイグラムに分けられます。 キエフはウクライナの首都、首都です 。 このアプローチでは、モデルは少なくとも、どの単語が一緒に立つことができ、どの単語が一緒にできないかを「理解」します。 これで、モデルに入力されたビッグプットの頻度はゼロになりました。
結論
アルゴリズムは良い結果を示しています。 弱点は辞書です。 Twitterのデータはほとんどが非公式であり、人々の名前、地名などであるため、辞書は多くの適切な候補者を排除します。 したがって、アルゴリズムの開発の方向の1つは、辞書の拒否です。 代わりに、トレーニングからの単語を使用できます。 2番目の弱点は列車セットです。 MLアルゴリズムではすべてがそれに依存しているため、できるだけ多くの関連データが必要です。 ここでは、オプションとして、同じtwitterから取得したデータのtrain-setを使用できます。
参照資料
ここから 5万8千語以上の辞書が取られています 。
訓練生として、Peter NorwigのWebサイトで100万語以上のファイルが見つかりました。 まだ面白いことがたくさんあります。
これらはすべてClojure言語で実装されました。 だから誰がgithubを気にします。