Loading article…
言語形態論および情報検索において、ステミングとは、屈折語（または派生語）を語幹、基本形、または語根形（一般的には書き言葉の形）に還元するプロセスです。語幹は、単語の形態論的な語根と同一である必要はありません。関連する単語が同じ語幹にマッピングされれば、通常は十分です。たとえこの語幹自体が有効な語根でなくても構いません。ステミングのアルゴリズムは、 1960年代からコンピュータ科学で研究されてきました。多くの検索エンジンは、同じ語幹を持つ単語を同義語として扱い、クエリ拡張の一種として、このプロセスを融合と呼びます。
単語の語幹を抽出するコンピュータプログラムまたはサブルーチンは、語幹抽出プログラム、語幹抽出アルゴリズム、または語幹抽出器と呼ばれることがあります。
英語の語幹「cat」を基準とする語幹抽出器は、 「cats」、「catlike」、「catty」などの文字列を識別するはずです。語幹抽出アルゴリズムは、 「fishing」、「fished」、「fisher」などの単語を「fish」という語幹に還元することもあります。語幹は必ずしも単語である必要はなく、例えばポーターアルゴリズムは「argue」、「arguged」、「argues」、「arguing」、 「argus 」を「argu」という語幹に還元します。
最初に発表されたステマーは、1968年にジュリー・ベス・ロビンスによって書かれた。 [ 1 ]この論文は、発表時期が早いという点で注目に値し、この分野のその後の研究に大きな影響を与えた。彼女の論文は、プリンストン大学のジョン・W・テューキー教授によるステミングアルゴリズムの3つの主要な試み、ジェラード・サルトン教授の指導の下、ハーバード大学のマイケル・レスクによって開発されたアルゴリズム、そしてカリフォルニア州ロスアルトスのR&Dコンサルタンツのジェームズ・L・ドルビーによって開発された3番目のアルゴリズムに言及している。
後に開発されたステマーはマーティン・ポーターによって作成され、1980年7月号の学術誌『 Program』に掲載された。このステマーは非常に広く使用され、英語のステミングにおける事実上の標準アルゴリズムとなった。ポーター博士は、ステミングと情報検索に関する業績により、2000年にトニー・ケント・ストリックス賞を受賞した。
Many implementations of the Porter stemming algorithm were written and freely distributed; however, many of these implementations contained subtle flaws. As a result, these stemmers did not match their potential. To eliminate this source of error, Martin Porter released an official free software (mostly BSD-licensed) implementation[2] of the algorithm around the year 2000. He extended this work over the next few years by building Snowball, a framework for writing stemming algorithms, and implemented an improved English stemmer together with stemmers for several other languages.
The Paice-Husk Stemmer was developed by Chris D Paice at Lancaster University in the late 1980s, it is an iterative stemmer and features an externally stored set of stemming rules. The standard set of rules provides a 'strong' stemmer and may specify the removal or replacement of an ending. The replacement technique avoids the need for a separate stage in the process to recode or provide partial matching. Paice also developed a direct measurement for comparing stemmers based on counting the over-stemming and under-stemming errors.
There are several types of stemming algorithms which differ in respect to performance and accuracy and how certain stemming obstacles are overcome.
A simple stemmer looks up the inflected form in a lookup table. The advantages of this approach are that it is simple, fast, and easily handles exceptions. The disadvantages are that all inflected forms must be explicitly listed in the table: new or unfamiliar words are not handled, even if they are perfectly regular (e.g. cats ~ cat), and the table may be large. For languages with simple morphology, like English, table sizes are modest, but highly inflected languages like Turkish may have hundreds of potential inflected forms for each root.
A lookup approach may use preliminary part-of-speech tagging to avoid overstemming.[3]
The lookup table used by a stemmer is generally produced semi-automatically. For example, if the word is "run", then the inverted algorithm might automatically generate the forms "running", "runs", "runned", and "runly". The last two forms are valid constructions, but they are unlikely..
接尾辞除去アルゴリズムは、活用形と語根の関係を表すルックアップテーブルに依存しません。代わりに、通常はより小さな「ルール」のリストが格納され、入力された単語の形に基づいてアルゴリズムがその語根の形を見つけるための道筋を示します。ルールの例としては、次のようなものがあります。
接尾辞除去アプローチは、保守担当者が言語学と形態論の課題と接尾辞除去ルールの符号化について十分な知識を持っていることを前提として、総当たりアルゴリズムよりも保守がはるかに簡単であるという利点があります。接尾辞除去アルゴリズムは、例外的な関係（「ran」と「run」など）を扱う際のパフォーマンスが低いため、粗雑だと見なされることがあります。接尾辞除去アルゴリズムによって生成されるソリューションは、例外がほとんどないよく知られた接尾辞を持つ語彙カテゴリに限定されます。しかし、すべての品詞にそのようなよく定式化されたルールセットがあるわけではないため、これは問題です。レンマ化は、この課題を改善しようとします。
接頭辞の削除も実装される可能性があります。もちろん、すべての言語が接頭辞や接尾辞を使用するわけではありません。
接尾辞除去アルゴリズムは、さまざまな理由で結果が異なる場合があります。その理由の1つは、アルゴリズムが出力語が与えられた言語の実際の単語である必要があるかどうかを制約するかどうかです。一部のアプローチでは、単語が実際に言語の語彙（言語内のすべての単語の集合）に存在することを要求しません。一方、接尾辞除去アプローチの中には、実際の単語として存在するすべての既知の形態素語根のデータベース（大規模なリスト）を保持するものがあります。これらのアプローチでは、決定を下す前に、そのリストに用語が存在するかどうかを確認します。通常、用語が存在しない場合は、代替アクションが実行されます。この代替アクションには、他のいくつかの基準が含まれる場合があります。出力用語が存在しない場合、アルゴリズムは代替の接尾辞除去ルールを試行する可能性があります。
同じ入力語に対して2つ以上の接尾辞除去ルールが適用される場合があり、どのルールを適用すべきか曖昧さが生じます。アルゴリズムは、（人手で、または確率的に）いずれかのルールに優先順位を割り当てる場合があります。あるいは、アルゴリズムは、一方のルールの適用によって存在しない語が生成され、もう一方の重複するルールでは存在しない語が生成されないため、一方のルールの適用を拒否する場合があります。たとえば、英語の単語friendliesが与えられた場合、アルゴリズムは接尾辞 iesを識別し、適切なルールを適用してfriendlという結果を得る可能性があります。friendlはおそらく辞書に存在しないため、ルールは拒否されます。
基本的な接尾辞除去の改良点の1つは、接尾辞置換の使用です。除去ルールと同様に、置換ルールは接尾辞を別の接尾辞に置き換えます。たとえば、ies をyに置き換えるルールが存在する可能性があります。これがアルゴリズムにどのように影響するかは、アルゴリズムの設計によって異なります。例として、アルゴリズムは、ies の接尾辞除去ルールと接尾辞置換ルールの両方が適用されることを認識する場合があります。除去ルールでは辞書に存在しない用語が生成されますが、置換ルールでは生成されないため、代わりに置換ルールが適用されます。この例では、friendlies はfriendl 'ではなくfriendlyになります。
さらに詳しく見ていくと、一般的な手法として、ルールを循環的に（コンピュータ科学者が言うところの再帰的に）適用する方法があります。この例のシナリオでは、接尾辞置換ルールを適用した後、2回目の処理で「friendly」という語に一致するルールを特定します。このとき、 「ly」を削除するルールが特定され、受け入れられる可能性が高いです。まとめると、「friendlies」は（置換によって）「friendly」となり、さらに（削除によって）「friend」となります。
この例は、ルールベースのアプローチと総当たりアプローチの違いを説明するのにも役立ちます。総当たりアプローチでは、アルゴリズムは何十万もの活用形の中から「friendlies」を探し出し、理想的には対応する語根「friend」を見つけます。一方、ルールベースのアプローチでは、前述の3つのルールを順番に適用して、同じ解に収束させます。総当たりアプローチは、検索アルゴリズムが解に直接アクセスできるのに対し、ルールベースのアプローチは複数の選択肢とその組み合わせを試してから、最も良さそうな結果を選択するため、処理速度が遅くなる可能性が高いでしょう。
単語の語幹を決定する問題に対するより複雑なアプローチは、語幹抽出法です。このプロセスでは、まず単語の品詞を決定し、品詞ごとに異なる正規化規則を適用します。言語によっては語幹抽出規則が品詞によって変化するため、語幹の探索を試みる前に品詞を最初に検出する必要があります。
このアプローチは、正しい語彙カテゴリー（品詞）を取得できることに大きく依存します。特定のカテゴリーの正規化ルールには重複がありますが、間違ったカテゴリーを識別したり、正しいカテゴリーを生成できなかったりすると、接尾辞除去アルゴリズムに比べてこのアプローチの利点が制限されます。基本的な考え方は、ステマーが語幹抽出対象の単語についてより多くの情報を把握できれば、より正確な正規化ルールを適用できるということです（接尾辞除去ルールとは異なり、語幹を変更することもできます）。
確率的アルゴリズムは、確率を用いて単語の語根形を識別する手法です。確率的アルゴリズムは、語根形と活用形の関係表に基づいて学習（「学習」）を行い、確率モデルを構築します。このモデルは通常、接尾辞除去や語幹抽出と同様の複雑な言語規則の形で表現されます。語幹抽出は、学習済みモデルに活用形を入力し、モデルが内部規則セットに従って語根形を生成することで行われます。これもまた、接尾辞除去や語幹抽出と同様の手法ですが、最も適切な規則を適用するか、語幹抽出を行って同じ単語を返すか、あるいは2つの異なる規則を順次適用するかといった判断は、出力単語が正解である確率が最も高くなる（つまり、不正解である確率が最も低くなる）という基準に基づいて行われます。
語形変化アルゴリズムの中には、複数の品詞に属する可能性のある単語に対して、それぞれの品詞に確率を割り当てるという確率的なものがあります。これは、周囲の単語（文脈）を考慮に入れる場合と入れない場合の両方があります。文脈自由文法は、このような追加情報を一切考慮に入れません。いずれの場合も、それぞれの品詞に確率を割り当てた後、最も可能性の高い品詞が選択され、そこから適切な正規化規則が入力単語に適用されて、正規化された（語幹）形が生成されます。
ハイブリッドアプローチでは、上記のアプローチのうち2つ以上を組み合わせて使用します。簡単な例としては、まず総当たり検索でルックアップテーブルを参照する接尾辞ツリーアルゴリズムが挙げられます。ただし、特定の言語における単語間の関係をすべて格納しようとするのではなく、ルックアップテーブルは小さく保たれ、「ran => run」のようなごく少数の「頻繁な例外」のみを格納するために使用されます。単語が例外リストに含まれていない場合は、接尾辞除去または語幹抽出を適用して結果を出力します。
In linguistics, the term affix refers to either a prefix or a suffix. In addition to dealing with suffixes, several approaches also attempt to remove common prefixes. For example, given the word indefinitely, identify that the leading "in" is a prefix that can be removed. Many of the same approaches mentioned earlier apply, but go by the name affix stripping. A study of affix stemming for several European languages can be found here.[5]
Such algorithms use a stem database (for example a set of documents that contain stem words). These stems, as mentioned above, are not necessarily valid words themselves (but rather common sub-strings, as the "brows" in "browse" and in "browsing"). In order to stem a word the algorithm tries to match it with stems from the database, applying various constraints, such as on the relative length of the candidate stem within the word (so that, for example, the short prefix "be", which is the stem of such words as "be", "been" and "being", would not be considered as the stem of the word "beside")..
While much of the early academic work in this area was focused on the English language (with significant use of the Porter Stemmer algorithm), many other languages have been investigated.[6][7][8][9][10]
Hebrew and Arabic are still considered difficult research languages for stemming. English stemmers are fairly trivial (with only occasional problems, such as "dries" being the third-person singular present form of the verb "dry", "axes" being the plural of "axe" as well as "axis"); but stemmers become harder to design as the morphology, orthography, and character encoding of the target language becomes more complex. For example, an Italian stemmer is more complex than an English one (because of a greater number of verb inflections), a Russian one is more complex (more noun declensions), a Hebrew one is even more complex (due to nonconcatenative morphology, a writing system without vowels, and the requirement of prefix stripping: Hebrew stems can be two, three or four characters, but not more), and so on.[11]
Multilingual stemming applies morphological rules of two or more languages simultaneously instead of rules for only a single language when interpreting a search query. Commercial systems using multilingual stemming exist.
語幹抽出アルゴリズムには、過剰語幹抽出と不足語幹抽出という2種類のエラーがあります。過剰語幹抽出とは、本来同じ語幹になるべきではない2つの活用語が同じ語幹に抽出されてしまうエラー（偽陽性）です。不足語幹抽出とは、本来同じ語幹になるべき2つの活用語が同じ語幹に抽出されないエラー（偽陰性）です。語幹抽出アルゴリズムは、これらのエラーをそれぞれ最小限に抑えるように設計されていますが、一方のエラーを減らすと他方のエラーが増える可能性があります。
例えば、広く使われているPorterの語幹抽出器は、「universal」「university」「universe」を「univers」と語幹抽出します。これは過剰な語幹抽出の一例です。これら3つの単語は語源的には関連していますが、現代における意味は大きく異なるため、検索エンジンで同義語として扱うと、検索結果の関連性が低下する可能性があります。
ポーターの語幹抽出器における語幹の不完全抽出の例としては、「alumnus」→「alumnu」、「alumni」→「alumni」、「alumna」/「alumnae」→「alumna」などが挙げられる。この英単語はラテン語の形態論を保持しているため、これらの類似語は混同されない。
語幹抽出は、基本的な意味が似ている単語をグループ化するための近似的な方法として用いられます。例えば、「daffodils」という単語を含むテキストは、「daffodil」（語尾にsがない）という単語を含むテキストと密接に関連していると考えられます。しかし、形態論的に同じ語幹を持つ単語でも、慣用的な意味が密接に関連していない場合もあります。「marketing」を検索しているユーザーは、「markets」という単語を含むドキュメントのほとんどでは満足せず、「marketing」という単語を含まないドキュメントに満足しないでしょう。
ステマーは、 Web検索エンジンなどのクエリシステムの要素として使用できます。しかし、英語のクエリシステムにおけるステミングの有効性はすぐにかなり限定的であることが判明し、このため初期の情報検索研究者はステミングを一般的に無関係とみなすようになりました。[ 12 ]代わりに、ステムではなくnグラムを検索する代替アプローチが使用される場合があります。また、ステマーは英語以外の言語でより大きな利点を提供する可能性があります。[ 13 ] [ 14 ]
ステミングは、ドメイン分析におけるドメイン語彙を決定するために使用されます。[ 15 ]
多くの商用企業は少なくとも1980年代からステミングを使用しており、多くの言語でアルゴリズム的および語彙的ステマーを開発してきました。[ 16 ] [ 17 ]
Snowballのステマーは、市販の語彙ステマーと比較され、結果は様々であった。[ 18 ] [ 19 ]
Google検索は2003年に単語ステミングを採用しました。[ 20 ]以前は「fish」で検索しても「fishing」は返されませんでした。他のソフトウェアの検索アルゴリズムは、単語ステミングの使用方法が異なります。単に部分文字列を検索するプログラムは、「fishing」の中に「fish」を見つけるのは当然ですが、「fishes」を検索すると「fish」という単語は見つかりません。
ステミングは、テキストマイニング分析を実行する前に、テキストを前処理するタスクとして使用されます。