純粋なPythonで検索エンジンを構築するステップバイステップ - 依存関係は不要

今日の情報爆発の時代において、検索エンジンは人々が情報にアクセスするための主要な手段となっています。GoogleやBingのような商用検索エンジンは、その背後に複雑な技術アーキテクチャを持っていますが、そのコアとなる原則は基本的な情報検索技術を通じて理解することができます。この記事では、Pythonの標準ライブラリのみを使用し、サードパーティの依存関係を一切持たずに、TF-IDFアルゴリズムに基づく英語検索エンジンをゼロから構築する方法を説明し、主要な転置インデックス構造をCSV形式で保存します。この実践を通して、検索エンジンの仕組みを深く理解し、テキスト処理、インデックス構築、関連性計算におけるコア技術を習得します。

検索エンジンのコアコンポーネント

完全な検索エンジンは通常、ドキュメント処理モジュール、インデックス構築モジュール、クエリ処理モジュール、ランキングモジュールの4つのコアモジュールで構成されています。サードパーティのライブラリに依存する実装とは異なり、純粋なPython実装では、各环节の詳細を手動で処理する必要があり、各ステップの背後にある原則をより深く理解できます。

ドキュメント処理モジュールは、生のテキストを計算に適した構造化データに変換し、トークン化、ノイズ除去（句読点など）、正規化（大文字小文字変換など）などの操作を行います。インデックス構築モジュールは検索エンジンのコアであり、各用語がどのドキュメントに現れるか、その位置を記録する転置インデックスを確立することで、高速なクエリを可能にします。クエリ処理モジュールは、ユーザー入力クエリを受け取り、ドキュメント処理と同じ正規化操作を実行して、インデックス内の用語と一致させます。ランキングモジュールは、TF-IDFアルゴリズムを使用して、クエリ用語と各ドキュメントの間の関連性スコアを計算し、スコアでソートされた結果を返します。

TF-IDFアルゴリズムの原則

TF-IDF（Term Frequency-Inverse Document Frequency）は、ドキュメントコレクションにおける用語の重要性を評価するために使用される統計的な手法です。そのコアとなるアイデアは、用語の重要性は、特定のドキュメントにおけるその頻度に比例し、ドキュメントコレクション全体におけるその頻度に反比例するということです。

用語頻度（TF）の計算

用語頻度とは、特定のドキュメントに用語が現れる回数を指します。ドキュメントの長さが結果に与える影響を避けるために、通常、正規化が適用されます。

TF(t,d) = ドキュメントdにおける用語tの出現回数 / ドキュメントdにおける用語の総数

たとえば、100個の用語を含むドキュメントで、「learning」が5回出現する場合、その用語頻度は5/100 = 0.05です。

逆ドキュメント頻度（IDF）の計算

逆ドキュメント頻度は、用語の識別力を測定し、次のように計算されます。

IDF(t) = log(ドキュメントの総数 / 用語tを含むドキュメントの数)

用語がほとんどのドキュメントに現れる場合、そのIDF値は低く、識別力が弱いことを示します。逆に、用語が少数のドキュメントにしか現れない場合、そのIDF値は高く、識別力が強いことを示します。たとえば、合計10個のドキュメントがあり、「machine」がそのうち3つに現れると仮定すると、そのIDF値はlog(10/3) ≈ 1.20397です。

TF-IDF値の計算

TF-IDF値は、用語頻度と逆ドキュメント頻度の積です。

TF-IDF(t,d) = TF(t,d) × IDF(t)

この値は、用語tがドキュメントdにおいてどれほど重要であるかを包括的に反映しており、ドキュメントとクエリの間の関連性を測定するための重要な指標です。

転置インデックスの設計

転置インデックスは、検索エンジンにおける高速なクエリのための重要なデータ構造であり、各用語と、それが現れるドキュメントと位置を記録します。純粋なPython実装では、合理的な転置インデックス構造を設計し、永続化のためにCSV形式で保存する必要があります。

転置インデックスの基本的な構造には、用語、ドキュメントID（doc_id）、および位置の3つの部分が含まれます。位置情報は、用語がドキュメントに現れる特定の場所を記録し、その後のフレーズクエリと近接クエリを容易にします。

CSVファイルの形式は次のとおりです。

term,doc_id,positions machine,0,"[1,5]" learning,0,"[2,8]" ...

この形式により、Pythonの標準csvモジュールを使用して読み書き操作を行うことができます。異なるドキュメントでの用語の各出現は、行として記録され、positionsフィールドは位置リストを文字列として格納します。

純粋なPythonによる実装の手順

次に、純粋なPythonを使用して、ドキュメントの前処理、転置インデックスの構築、TF-IDFの計算、クエリの処理、および結果のランキングを含む、TF-IDFに基づく英語検索エンジンをゼロから実装する方法について詳しく説明します。

ステップ1：ドキュメントの前処理

ドキュメントの前処理では、生のテキストを構造化されたデータに変換します。これには、主に次の操作が含まれます。

大文字小文字の変換：「Machine」と「machine」を異なる用語として扱わないように、すべてのテキストを小文字に変換します。
句読点の削除：ノイズを減らすために、テキストから句読点を削除します。
トークン化：連続したテキストを個々の用語に分割します。
ストップワードの削除：「the」や「and」のような実質的な意味を持たない高頻度の単語をフィルタリングします。
簡単なステミング：用語をその語幹形式に減らします（簡略化された実装）。

実装コードは次のとおりです。

import string

# 英語のストップワードセットを定義します
STOP_WORDS = {
    'a', 'an', 'and', 'the', 'or', 'of', 'to', 'in', 'for', 'on', 'with',
    'at', 'by', 'i', 'you', 'he', 'she', 'it', 'we', 'they', 'me', 'him',
    'her', 'us', 'them', 'my', 'your', 'his', 'its', 'our', 'their', 'this',
    'that', 'these', 'those', 'is', 'are', 'was', 'were', 'be', 'been', 'being',
    'have', 'has', 'had', 'do', 'does', 'did', 'will', 'would', 'shall', 'should',
    'may', 'might', 'must', 'can', 'could', 'as', 'but', 'if', 'or', 'because',
    'until', 'while', 'of', 'at', 'by', 'for', 'with', 'about', 'against', 'between',
    'into', 'through', 'during', 'before', 'after', 'above', 'below', 'from', 'up',
    'down', 'in', 'out', 'on', 'off', 'over', 'under', 'again', 'further', 'then',
    'once', 'here', 'there', 'when', 'where', 'why', 'how', 'all', 'any', 'both',
    'each', 'few', 'more', 'most', 'other', 'some', 'such', 'no', 'nor', 'not',
    'only', 'own', 'same', 'so', 'than', 'too', 'very'
}

def preprocess_text(text):
    """テキストの前処理：大文字小文字の変換、句読点の削除、トークン化、ストップワードの削除"""
    # 小文字に変換
    text = text.lower()
    
    # 句読点を削除
    translator = str.maketrans('', '', string.punctuation)
    text = text.translate(translator)
    
    # トークン化（単純なスペース分割。より複雑なロジックを実際のアプリケーションで使用できます）
    tokens = text.split()
    
    # ストップワードと空文字列を削除
    tokens = [token for token in tokens if token not in STOP_WORDS and token.strip() != '']
    
    # 簡単なステミング（簡略化されたバージョン）
    tokens = [stem_token(token) for token in tokens]
    
    return tokens

def stem_token(token):
    """簡単なステミング関数（より複雑なアルゴリズムを実際のアプリケーションで使用できます）"""
    # 一般的な接尾辞を処理します
    suffixes = ['ing', 'ly', 'ed', 'es', 's']
    for suffix in suffixes:
        if token.endswith(suffix) and len(token) > len(suffix):
            return token[:-len(suffix)]
    return token

# 前処理関数をテストします
sample_text = "Machine learning is a subset of artificial intelligence focused on developing algorithms that learn from data."
processed_tokens = preprocess_text(sample_text)
print("前処理された用語：", processed_tokens)

この前処理関数は、基本的なテキストのクリーニングと正規化を実装し、その後のインデックス構築とTF-IDF計算の基礎を築きます。ここでのトークン化とステミングは簡略化された実装であることに注意してください。精度を向上させるために、より複雑なアルゴリズムを実際のアプリケーションで使用できます。

ステップ2：転置インデックスを構築し、CSVとして保存

転置インデックスを構築するプロセスには、すべてのドキュメントを反復処理し、各用語が現れるドキュメントIDと位置情報を記録し、結果をCSVファイルとして保存することが含まれます。

import csv
from collections import defaultdict

def build_inverted_index(documents):
    """転置インデックスを構築し、CSVファイルとして保存します"""
    inverted_index = defaultdict(list)  # 構造：{term: [(doc_id, positions), ...]}
    
    for doc_id, doc in enumerate(documents):
        # ドキュメントを前処理します
        tokens = preprocess_text(doc)
        
        # 現在のドキュメント内の各用語の位置を記録します
        term_positions = defaultdict(list)
        for pos, term in enumerate(tokens):
            term_positions[term].append(pos)
        
        # 転置インデックスを更新します
        for term, positions in term_positions.items():
            inverted_index[term].append((doc_id, positions))
    
    # 転置インデックスをCSVファイルとして保存します
    with open('inverted_index.csv', 'w', newline='', encoding='utf-8') as f:
        writer = csv.writer(f)
        writer.writerow(['term', 'doc_id', 'positions'])
        for term, doc_info in inverted_index.items():
            for doc_id, positions in doc_info:
                # 格納するために位置リストを文字列に変換します
                positions_str = str(positions)
                writer.writerow([term, doc_id, positions_str])
    
    return inverted_index

# サンプルのドキュメントコレクション
documents = [
    "Machine learning is a subset of artificial intelligence focused on developing algorithms that learn from data.",
    "Artificial intelligence involves creating systems that can perform tasks requiring human intelligence.",
    "Deep learning is a type of machine learning based on artificial neural networks with multiple layers.",
    "Natural language processing allows computers to understand and generate human language.",
    "Computer vision enables machines to interpret and understand the visual world.",
    "Reinforcement learning is an area of machine learning concerned with how agents take actions in an environment.",
    "Supervised learning algorithms learn from labeled training data to make predictions on new data.",
    "Unsupervised learning deals with unlabeled data, finding patterns and structures within it.",
    "A neural network is a computational model inspired by the human brain's structure and function.",
    "Big data refers to large and complex data sets that require advanced processing techniques."
]

# 転置インデックスを構築します
inverted_index = build_inverted_index(documents)
print(f"転置インデックスが構築されました。{len(inverted_index)}個の用語が含まれています")

このコードは、最初に各ドキュメントを反復処理し、前処理し、ドキュメント内の各用語の位置を記録し、この情報を転置インデックスに整理し、CSVファイルとして保存します。転置インデックスは、キーが用語で、値がドキュメントIDと位置リストを含むタプルのリストである辞書として構造化されています。

ステップ3：TF-IDF値を計算する

TF-IDF値を計算するには、まず用語頻度と逆ドキュメント頻度をカウントし、次にそれらの積を計算する必要があります。純粋なPythonの実装では、これらの計算を手動で実行する必要があります。

def calculate_tfidf(documents, inverted_index):
    """各ドキュメント内の各用語のTF-IDF値を計算します"""
    num_docs = len(documents)
    tfidf = {}  # 構造：{doc_id: {term: tfidf_value, ...}, ...}
    
    # 各ドキュメントの用語の総数を計算します
    doc_lengths = []
    for doc in documents:
        tokens = preprocess_text(doc)
        doc_lengths.append(len(tokens))
    
    # 各用語のドキュメント頻度（用語を含むドキュメントの数）を計算します
    doc_freq = {term: len(entries) for term, entries in inverted_index.items()}
    
    # TF-IDFを計算します
    for term, entries in inverted_index.items():
        # IDFを計算します
        idf = math.log(num_docs / (doc_freq[term] + 1))  # ゼロ除算を避けるために+1
        
        for doc_id, positions in entries:
            # TFを計算します
            tf = len(positions) / doc_lengths[doc_id] if doc_lengths[doc_id] > 0 else 0
            
            # TF-IDFを計算します
            tfidf_value = tf * idf
            
            # 結果を格納します
            if doc_id not in tfidf:
                tfidf[doc_id] = {}
            tfidf[doc_id][term] = tfidf_value
    
    return tfidf

import math  # 対数計算のためにmathライブラリをインポートします

# TF-IDF値を計算します
tfidf_scores = calculate_tfidf(documents, inverted_index)
print("TF-IDF計算が完了しました")

このコードは、最初に各ドキュメントの長さ（前処理後の用語の総数）と各用語のドキュメント頻度を計算し、次に用語頻度と逆ドキュメント頻度をそれぞれ計算し、最後にそれらの積を計算してTF-IDF値を取得します。計算結果は、その後のクエリで簡単に使用できるように、ネストされた辞書に格納されます。

ステップ4：クエリを処理して結果を返す

クエリ処理モジュールは、ユーザー入力クエリを前処理し、転置インデックスに基づいてクエリ用語を含むドキュメントを検索し、クエリと各ドキュメントの間の関連性スコアを計算し、スコアでソートされた結果を返す必要があります。

def search(query, documents, inverted_index, tfidf_scores, top_n=3):
    """クエリを処理して、最も関連性の高いドキュメントを返します"""
    # クエリを前処理します
    query_terms = preprocess_text(query)
    if not query_terms:
        return []
    
    # 少なくとも1つのクエリ用語を含むドキュメントを取得します
    relevant_docs = set()
    for term in query_terms:
        if term in inverted_index:
            for doc_id, _ in inverted_index[term]:
                relevant_docs.add(doc_id)
    relevant_docs = list(relevant_docs)
    
    # クエリと各関連ドキュメントの間の関連性スコアを計算します
    scores = []
    for doc_id in relevant_docs:
        score = 0.0
        for term in query_terms:
            if term in tfidf_scores.get(doc_id, {}):
                score += tfidf_scores[doc_id][term]
        
        # スコアを正規化します（クエリ用語の数で除算します）
        score /= len(query_terms)
        scores.append((doc_id, score))
    
    # スコアでソートします
    scores.sort(key=lambda x: x[1], reverse=True)
    
    # 上位N件の結果を返します
    results = []
    for doc_id, score in scores[:top_n]:
        if score > 0:
            results.append({
                'document': documents[doc_id],
                'score': score,
                'doc_id': doc_id
            })
    
    return results

# 検索機能をテストします
import math  # mathライブラリがインポートされていることを確認します
query = "machine learning"
results = search(query, documents, inverted_index, tfidf_scores)
print(f"クエリ：{query}")
for i, result in enumerate(results, 1):
    print(f"\n 結果 {i} (スコア：{result['score']:.4f})：")
    print(result['document'])

このコードは、最初にクエリ用語を前処理し、次にクエリ用語を含むすべてのドキュメントを検索し、各ドキュメントとクエリの間の関連性スコアを計算し（ここでは単純な合計法を使用）、最後にスコアでソートされた結果を返します。

ステップ5：CSVから転置インデックスをロードする

永続化のために、CSVファイルから転置インデックスをロードできる必要があります。

def load_inverted_index_from_csv(filename):
    """CSVファイルから転置インデックスをロードします"""
    inverted_index = defaultdict(list)
    
    with open(filename, 'r', encoding='utf-8') as f:
        reader = csv.reader(f)
        next(reader)  # ヘッダーをスキップします
        
        for row in reader:
            term = row[0]
            doc_id = int(row[1])
            
            # 位置文字列をリストに戻します
            positions = eval(row[2])  # 注：evalにはセキュリティリスクがあります。実際のアプリケーションでは、より安全なメソッドを使用してください
            
            inverted_index[term].append((doc_id, positions))
    
    return inverted_index

# 転置インデックスのロードをテストします
loaded_index = load_inverted_index_from_csv('inverted_index.csv')
print(f"CSVからロードされた転置インデックスには、{len(loaded_index)}個の用語が含まれています")

このコードは、CSVファイルから転置インデックスデータを読み取り、位置情報を文字列からリストに変換し、転置インデックス構造を再構築します。eval関数を使用するとセキュリティリスクが発生することに注意してください。実際のアプリケーションでは、より安全なメソッド（正規表現解析など）を使用して、位置文字列を変換できます。

パフォーマンスの最適化と拡張

純粋なPythonで実装された検索エンジンは、大規模なドキュメントを処理する際にパフォーマンスの問題が発生する可能性があります。次に、いくつかの最適化の提案を示します。

インデックス圧縮：転置インデックス内の位置情報は、デルタエンコーディングなどの方法を使用して圧縮し、ストレージスペースとメモリ使用量を削減できます。
キャッシュメカニズム：頻繁にアクセスされるインデックスの部分をメモリにキャッシュして、ディスクI/O操作を削減します。
並列計算：時間のかかるTF-IDF計算などの操作を実行する場合、Pythonのmultiprocessingモジュールを使用して並列計算を行います。
クエリの最適化：複数の用語を含むクエリの場合、最初に関連性を計算する前に、すべてのクエリ用語（交差）を含むドキュメントを検索して、計算を削減します。

さらに、検索エンジンの機能を拡張して、フレーズクエリ、近接クエリ、ブールクエリなどをサポートし、検索精度と柔軟性を向上させることができます。

実際のアプリケーションでの課題

実際のアプリケーションでは、純粋なPythonで実装された検索エンジンは、次の課題に直面する可能性があります。

パフォーマンスの制限：C++などのコンパイル済み言語と比較して、Pythonの実行効率は低く、大規模なデータを処理する際にボトルネックが発生する可能性があります。
機能の制限：純粋なPythonの実装は、語義の曖昧性解消やエンティティ認識などの複雑な自然言語処理タスクに苦労します。
スケーラビリティ：ドキュメントと語彙の数が増えるにつれて、インデックス構造が急速に拡張され、より複雑な分散ストレージとコンピューティングアーキテクチャが必要になります。

したがって、実際の検索エンジン開発では、Pythonの使いやすさと他の高性能言語の利点を組み合わせて、ハイブリッドアーキテクチャを備えたシステムを構築することが一般的です。

結論

この記事を通して、サードパーティのライブラリに依存せずに、TF-IDFに基づく英語検索エンジンをゼロから構築し、主要な転置インデックスをCSV形式で保存しました。このプロセスにより、ドキュメントの前処理、転置インデックスの構築、TF-IDFの計算、クエリの処理など、検索エンジンのコア原則と実装の詳細を深く理解することができました。

この実装は比較的単純ですが、最新の検索エンジンの基本的なフレームワークをカバーしています。この基盤の上に、機能をさらに拡張し、パフォーマンスを最適化して、より強力な検索システムを構築できます。学術研究であろうと実用的なアプリケーションであろうと、これらの基本的な原則を理解することは、情報検索技術の知識を深めるための重要なステップです。

この記事が、情報検索の分野への扉を開き、検索エンジン技術を探求することへの関心と欲求を刺激することを願っています。情報爆発の時代において、情報検索技術を習得することは、情報をより効率的に取得するのに役立つだけでなく、データマイニングや人工知能などの分野の研究のための強固な基盤を提供します。