Zellig Harris と分布的分析

計算ステミングの起源

1955年に、言語学者Zellig HarrisはFrom Phoneme to Morphemeを発表し、単語内の意味のある単位（形態素）の間の境界を見つける方法を説明しました。

彼の洞察は分布的でした。英語の単語の大規模なコーパスを見ると、語幹と接尾辞の間の境界が統計的信号として現れます。

後続多様性メソッド

単語の任意のプレフィックスについて、コーパス内でそれに続く異なる文字の数を数えます。Harris はこれを後続多様性と呼びました。

コーパスで「work」プレフィックスを含む単語を考えます。 worked, worker, working, works, workshopを含む。

「work」の後、4つの異なる文字が続く可能性があります。多様性が急増します。そのスパイクは形態素境界をマークします。語幹はworkであり、その後のすべてが接尾辞です。

これは1955年には画期的でした。言語学的規則なし、辞書なし。ただカウントします。Harris は言語の構造が分布を通じて自らを明かすことを示しました。

後続多様性の理解

Harris のメソッドはどの言語でも機能します。文法を知る必要はありません。統計は形態素の境界を明かします。

実際には、純粋な後続多様性は大規模なコーパスと慎重なピーク検出が必要です。後の研究者: Lovins (1968)、Porter (1980) は、コーパスから後続多様性を計算する代わりに、接尾辞ルールを直接エンコードするルールベースの接尾辞の除去へのアプローチを簡略化しました。

今日は、Harris の洞察に触発されたルールベースの接尾辞ストリッパーを構築します。接尾辞を明示的に定義してから、単語から削り落とします。これはほとんどの本番ステマーがどのように機能するかです。

あなたの最初の接尾辞ストリッパー

コードを書きましょう

シンプルに始めます。この順序で接尾辞を削り落とすstemという関数を書いてください:

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

ルール:

- まず単語を小文字に変換してください

- 1つの接尾辞のみを削り落とします（上記の順序での最初のマッチ）

- 残りの語幹が少なくとも3文字の長さの場合のみ削り落とします

- 語幹を返します

例:

def stem(word):
    word = word.lower()
    # あなたの接尾辞ストリップロジックはここに
    return word

エッジケースの処理

ステマーをより賢くする

あなたの基本的なストリッパーは問題があります: running → runn & hoping → hop。2つの改善が必要です:

1. ダブルコンソナント クリーンアップ: -ing または -ed を削り落とすと、末尾にダブルコンソナントが残ります（runnのような）、最後の文字を削除してください → run

2. サイレント-e の復元: -ing を削り落とすと語幹が子音で終わります（母音ではなく）、& 元々はサイレントeを持っていたかもしれません（hopingからhopのような）、eを戻してください → hope

サイレント-e ルールについては、シンプルに保ちます: -ing を削り落とした後、語幹が3+文字で、子音で終わり、& 2番目から最後の文字が母音（hop、mak、takのようなパターン）の場合、eを戻します。

また、これらの新しい接尾辞も追加してください（-ing、-ed、-ly、-s の前にチェック）:

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

更新された接尾辞の優先度: -tion、-ness、-ment、-able、-ible、-ing、-ed、-ly、-s

最小語幹長ルールを保ち続ける: 残りの語幹が3+文字の場合のみ削り落とします。

-ies & -ier ルール

より多くの形態素論

英語には別の一般的なパターンがあります: -yで終わる単語は、活用されるとき-ies、-ied、または-ierに変わります。

これらのルールを-s & -ed チェック前に追加してください:

- -ies → 削除 & i を追加（babies → babi）

- -ied → 削除 & i を追加（carried → carri）

- -ier → 削除 & i を追加（earlier → earli）

同じ最小語幹長ルール: 結果が3+文字の場合のみ変換します。

なぜテストが必要か

テストはオプションではありません

あなたは機能するステマーを持っています。それが実際に機能することをどのように知っていますか? 今のところ、いくつかの例を手動で実行しています。それはスケールしません。

プロフェッショナルソフトウェアは3つのテストレベルを使用します:

単体テスト: 既知の入力と期待される出力を持つ、分離で1つの関数をテストします。高速、多数、具体的。

統合テスト: 複数のコンポーネントが一緒に機能することをテストします。ステマーについて、これは単語のバッチをテストし、結果が一貫していることを確認することを意味します。

機能テスト: ユーザーがするのと同じように、外側からシステムをテストします。ステマーについて、これは実際のテキストをフィードし、検索のような実際のユースケースの出力が意味をなすことを確認することを意味します。

あなたはすべて3つを書きます。

単体テストを書く

単体テスト

次をカバーする少なくとも15個のテストケースで run_unit_tests という関数を書いてください:

1. 基本的な接尾辞削除: -ing、-ed、-ly、-s で終わる単語

2. 複雑な接尾辞: -tion、-ness、-ment、-able、-ible

3. Y-活用: -ies、-ied、-ier

4. エッジケース: 削除されるべきではない短い単語、接尾辞のない単語、既に削減された単語

5. ダブルコンソナント クリーンアップ: running → run、sitting → sit

6. サイレント-e 復元: hoping → hope

7. 大文字不感性: 大文字の入力は小文字にする必要があります

このようなテストを構造化します:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... at least 15 test cases
    ]
    passed = 0
    failed = 0
    for word, expected in tests:
        result = stem(word)
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f'FAIL: stem({word}) = {result}, expected {expected}')
    print(f'{passed}/{passed + failed} unit tests passed')
    return failed == 0

統合テストを書く

統合テスト

単体テストは個々の入力を確認します。統合テストは、コンポーネントが一緒に正しく機能することを確認します。

ステマーについて、重要な統合プロパティは一貫性です: 同じ単語を2回削減すると、同じ結果が得られます。そして、一緒にグループ化されるべき単語は同じ語幹を生成する必要があります。

次をテストする run_integration_tests という関数を書いてください:

1. イデムポテンシー: 既に削減された単語を削減すると同じ語幹が返されるべきです。すべての単語に対して stem(stem(word)) == stem(word) です。

2. グループ化: 語幹を共有すべき単語は実際に行います。少なくとも3つの単語ファミリーをテストしてください（例えば、run/runs/running/runner はすべて語幹を共有するべき）。

3. バッチ処理: 20以上の単語のリストを処理し、クラッシュ、空の文字列、なし値がないことを確認します。

def run_integration_tests():
    # テスト1: イデムポテンシー
    # テスト2: 単語ファミリーグループ化
    # テスト3: バッチ安定性
    ...

機能テストを書く

機能テスト

機能テストは、システムが意図したユースケースのために機能することを確認します。あなたのステマーは検索を改善するために存在します: そのようなテストです。

run_functional_tests という関数を書いてください:

1. 検索シミュレーション: ドキュメント文字列のリストと照会単語が与えられたとき、ドキュメントと照会の両方を削減してから、削減された照会条件がドキュメントに表示されるかどうかを確認します。「running」を検索すると、「run」と「runner」を含むドキュメントが見つかることをテストします。

2. 精度チェック: ステミングが無関係な単語を誤ってグループ化しないことを確認してください。「university」と「universe」は語幹を共有する可能性があります: あなたのステマーがこれを処理するかどうかを確認してください（それらをグループ化することは問題ありません。動作を文書化してください）。

3. 実際のテキスト処理: 実際の英語テキストの段落のすべての単語を削減してください。出力が合理的であることを確認してください。空の文字列なし、クラッシュなし、出力は入力と同じ数の単語を持ちます。

def run_functional_tests():
    # テスト1: 検索が関連ドキュメントを見つけます
    # テスト2: 精度: 過度削減をチェック
    # テスト3: 実際のテキスト処理
    ...

あなたが構築したもの

あなたが構築したもの

次を使用して動作する英語ステマーを実装しました:

- 12の接尾辞ルール (-tion、-ness、-ment、-able、-ible、-ies、-ied、-ier、-ing、-ed、-ly、-s)

- ダブルコンソナント クリーンアップ

- サイレント-e 復元

- 単体テスト、統合テスト、& 機能テスト

系統

あなたのステマーは、1955年のZellig Harris で始まる仕事のラインを下ります:

- Harris (1955): 形態素の境界が統計的信号として表示されることを発見（後続多様性）

- Lovins (1968): 最初に発表されたステミングアルゴリズム、294の接尾辞ルール

- Porter (1980): 5つのステップで約60のルールに簡略化、数十年間標準になりました

- Snowball (2001): Porter のフレームワークが複数言語に一般化されました

- あなたのステマー (今日): 12のルール、同じコアプリンシップ

次に何ができるか

- 完全なPorterアルゴリズムを実装してください（それはよく文書化されている優れた運動です）

- あなたのステマーをC にポートしてください 100倍の速度改善のため

- あなたのステマーを使用してテキストファイルをインデックスおよびクエリする簡単な検索エンジンを構築してください

- あなたのステマーの出力をNLTK のPorterStemmerと比較して精度を測定してください

今日書いたコードは、地球上のすべての検索エンジン内で実行される同じ基本的な操作です。1日の仕事として悪くありません。