ピュア Node.js を使ってゼロから英語検索エンジンを構築する：原理から CSV 逆インデックスの実装まで

情報爆発の時代において、検索エンジンは人々が情報にアクセスするための中心的なツールとなっています。Google から Bing まで、これらの大規模検索エンジンは複雑な技術アーキテクチャによって支えられていますが、その核心となる原則は基本的な技術スタックを使用して実装できます。この記事では、サードパーティライブラリを使用せずに、ピュア Node.js を使用して TF-IDF アルゴリズムに基づいた英語検索エンジンをゼロから構築し、逆インデックスを CSV ファイルに保存する方法を説明します。この実践を通じて、情報検索の中核となるメカニズムを深く理解し、テキスト処理、重み計算、インデックス構築の主要な技術を習得します。

検索エンジンの基礎と TF-IDF

検索エンジンは本質的に情報フィルタリングシステムであり、その核心的な機能は、ユーザーのクエリを受け取り、膨大なドキュメントから最も関連性の高い結果を迅速に見つけ出し、それらをランク付けすることです。現代の検索エンジンは、クローラー（データ取得）、インデクサー（検索構造の構築）、リトリーバー（クエリ処理）、ランキングアルゴリズム（結果の最適化）の 4 つのコアモジュールで構成されています。私たちの簡略化されたバージョンでは、インデクサーとリトリーバーに焦点を当て、ローカルドキュメントをデータソースとして使用します。

TF-IDF (Term Frequency-Inverse Document Frequency) は、情報検索の分野における古典的な重み付けアルゴリズムであり、1972 年にカレン・スパルク・ジョーンズによって提案され、現在でもさまざまなテキストシステムで広く使用されています。その核心的な考え方は、ドキュメントにおける単語の重要性は、そのドキュメント内での出現頻度に比例し、すべてのドキュメントでの出現頻度に反比例するというものです。

Term Frequency (TF): 現在のドキュメントで単語が出現する回数を、ドキュメント内の単語の総数で割ったものです。式は TF(t,d) = count(t,d) / totalTerms(d) です。たとえば、「machine」という単語が合計 100 語のドキュメントに 5 回出現する場合、TF 値は 0.05 になります。
Inverse Document Frequency (IDF): 単語を含むドキュメントの数の逆数の対数です。式は IDF(t) = log(totalDocs / docsWithTerm(t)) です。コーパスに 1000 個のドキュメントがあり、そのうち 20 個に「learning」が含まれている場合、IDF 値は log(1000/20) = log(50) ≈ 3.912 です。

この 2 つを掛け合わせると TF-IDF(t,d) = TF(t,d) × IDF(t) になります。この値が高いほど、単語が現在のドキュメントをより代表していることを意味します。検索中、クエリ用語とドキュメント間の TF-IDF ベクトル類似度（コサイン類似度など）を計算することで、結果のランキングを実現できます。

ピュア Node.js による実装ステップ

環境準備とプロジェクト構造

このプロジェクトは Node.js ランタイム (v14 以上で十分) にのみ依存しており、npm パッケージをインストールする必要はありません。次のディレクトリ構造を作成します。

tfidf-search/
├── corpus/         # 英語ドキュメントを保存する
│   ├── doc1.txt
│   ├── doc2.txt
│   └── ...
├── index/          # インデックスファイルを保存する
│   └── inverted.csv
├── src/
│   ├── indexer.js  # インデックス構築プログラム
│   └── searcher.js # 検索プログラム
└── run.js          # エントリファイル

corpus ディレクトリは、検索対象の英語ドキュメントを保存し、index ディレクトリは逆インデックスの CSV ファイルを保存するために使用され、src にはコア実装コードが含まれています。

1. テキストデータ処理

テキスト処理は検索エンジンの基礎であり、ドキュメントの読み取り、クリーニング、トークン化が必要です。src/indexer.js を作成し、基本的な処理関数を実装します。

// ドキュメントコンテンツを読み取る
const fs = require('fs');
const path = require('path');

function readDocuments(corpusPath) {
  const docs = [];
  const files = fs.readdirSync(corpusPath);
  
  for (const file of files) {
    if (file.endsWith('.txt')) {
      const content = fs.readFileSync(
        path.join(corpusPath, file), 
        'utf8'
      );
      docs.push({
        id: file.replace('.txt', ''),
        content: content
      });
    }
  }
  return docs;
}

テキストのクリーニングには、句読点の削除、小文字への変換、トークン化が含まれます。英語のトークン化は比較的簡単で、スペースで分割することで実行できますが、特別なケースに対処する必要があります。

function cleanText(text) {
  // HTML タグがある場合は削除
  let cleaned = text.replace(/<[^>]*>/g, ' ');
  // 小文字に変換
  cleaned = cleaned.toLowerCase();
  // 句読点と特殊文字を削除
  cleaned = cleaned.replace(/[^a-z0-9\s]/g, ' ');
  // 複数のスペースを 1 つにマージ
  cleaned = cleaned.replace(/\s+/g, ' ').trim();
  return cleaned;
}

function tokenize(text) {
  return cleanText(text).split(' ');
}

2. TF-IDF 計算の実装

Term Frequency (TF) の計算

TF 計算では、ドキュメント内の各単語の頻度をカウントする必要があります。以下のように実装します。

function calculateTF(tokens) {
  const tf = {};
  const totalTerms = tokens.length;
  
  for (const token of tokens) {
    if (token) { // 空の文字列をスキップ
      tf[token] = (tf[token] || 0) + 1;
    }
  }
  
  // 頻度 (単語数 / 総単語数) に変換
  for (const term in tf) {
    tf[term] = tf[term] / totalTerms;
  }
  
  return tf;
}

Inverse Document Frequency (IDF) の計算

IDF では、最初に各単語を含むドキュメントの数をカウントする必要があります。

function calculateDF(docs) {
  const df = {};
  const totalDocs = docs.length;
  
  for (const doc of docs) {
    const tokens = new Set(tokenize(doc.content)); // 重複排除
    for (const token of tokens) {
      if (token) {
        df[token] = (df[token] || 0) + 1;
      }
    }
  }
  
  // IDF を計算: log(ドキュメントの総数 / 用語を含むドキュメントの数)
  const idf = {};
  for (const term in df) {
    idf[term] = Math.log(totalDocs / df[term]);
  }
  
  return idf;
}

ドキュメントベクトルの生成

TF と IDF を組み合わせて、各ドキュメントのベクトルを生成します。

function generateDocVectors(docs, idf) {
  const docVectors = {};
  
  for (const doc of docs) {
    const tokens = tokenize(doc.content);
    const tf = calculateTF(tokens);
    const vector = {};
    
    for (const term in tf) {
      vector[term] = tf[term] * idf[term] || 0;
    }
    
    docVectors[doc.id] = vector;
  }
  
  return docVectors;
}

3. 逆インデックスの構築と CSV ストレージ

逆インデックスは検索エンジンの中核となるデータ構造であり、用語と、重みとともに用語を含むドキュメントのリストとの間のマッピングを保存します。その構造は通常、term,docId1,docId2,... です。

function buildInvertedIndex(docVectors) {
  const index = {};
  
  // メモリ内逆インデックスを構築
  for (const docId in docVectors) {
    const vector = docVectors[docId];
    for (const term in vector) {
      if (!index[term]) {
        index[term] = [];
      }
      index[term].push({
        docId,
        weight: vector[term]
      });
    }
  }
  
  // CSV 形式に変換
  let csvContent = 'term,documents\n';
  for (const term in index) {
    const docsStr = index[term]
      .map(item => `${item.docId}:${item.weight.toFixed(6)}`)
      .join(';');
    csvContent += `"${term}",${docsStr}\n`;
  }
  
  return csvContent;
}

// インデックスを CSV ファイルに保存
function saveIndex(csvContent, indexPath) {
  fs.writeFileSync(indexPath, csvContent, 'utf8');
}

CSV 形式を選択する理由は、プレーンテキストの読みやすさが強く、実装が簡単（シリアル化ライブラリは不要）、Excel などのツールで直接解析できることです。ただし、その欠点は、クエリ中にフルテキストスキャンが必要になることであり、後でより効率的な形式に最適化できます。

4. 完全なインデックス構築プロセス

上記の関数をインデックス構築プロセスに統合します。

async function buildIndex(corpusPath, indexPath) {
  try {
    console.log('ドキュメントを読み取っています...');
    const docs = readDocuments(corpusPath);
    
    console.log('ドキュメント頻度 (DF) を計算しています...');
    const idf = calculateDF(docs);
    
    console.log('ドキュメントベクトルを生成しています...');
    const docVectors = generateDocVectors(docs, idf);
    
    console.log('逆インデックスを構築しています...');
    const csvContent = buildInvertedIndex(docVectors);
    
    console.log('インデックスを CSV に保存しています...');
    saveIndex(csvContent, indexPath);
    
    console.log(`インデックス構築が完了しました。${docs.length} 個のドキュメントを処理しました`);
  } catch (error) {
    console.error('インデックス構築に失敗しました:', error);
  }
}

module.exports = { buildIndex };

5. 検索機能の実装

検索プログラムは、インデックスのロード、クエリの解析、類似度の計算、および結果の返却を行う必要があります。

// src/searcher.js
const fs = require('fs');
const path = require('path');

// CSV インデックスをロードし、メモリ内オブジェクトに変換
function loadIndex(indexPath) {
  const index = {};
  const csvContent = fs.readFileSync(indexPath, 'utf8');
  const lines = csvContent.split('\n');
  
  // ヘッダーをスキップ
  for (let i = 1; i < lines.length; i++) {
    const line = lines[i].trim();
    if (!line) continue;
    
    // CSV 行を解析 (引用符付きのケースを処理)
    const [termPart, docsPart] = line.split(',');
    const term = termPart.replace(/"/g, ''); // 引用符を削除
    
    if (docsPart) {
      index[term] = docsPart.split(';').map(item => {
        const [docId, weight] = item.split(':');
        return { docId, weight: parseFloat(weight) };
      });
    }
  }
  
  return index;
}

// クエリベクトルを計算
function getQueryVector(query, idf) {
  const tokens = tokenize(query);
  const tf = calculateTF(tokens);
  const vector = {};
  
  for (const term in tf) {
    vector[term] = tf[term] * (idf[term] || 0);
  }
  
  return vector;
}

// 検索を実行
function search(query, index, idf) {
  const queryVector = getQueryVector(query, idf);
  const results = {};
  
  // ドキュメントスコアを累積
  for (const term in queryVector) {
    if (index[term]) {
      const queryWeight = queryVector[term];
      for (const doc of index[term]) {
        // 簡単な類似性計算: 重み積の合計
        const score = (results[doc.docId] || 0) + (queryWeight * doc.weight);
        results[doc.docId] = score;
      }
    }
  }
  
  // ソートされた配列に変換
  return Object.entries(results)
    .map(([docId, score]) => ({ docId, score }))
    .sort((a, b) => b.score - a.score);
}

module.exports = { loadIndex, search };

6. エントリプログラムの実装

プログラムエントリとして run.js を作成します。インデックス構築と検索の 2 つのモードをサポートします。

const { buildIndex } = require('./src/indexer');
const { loadIndex, search } = require('./src/searcher');
const { calculateDF, readDocuments } = require('./src/indexer');

const CORPUS_PATH = path.join(__dirname, 'corpus');
const INDEX_PATH = path.join(__dirname, 'index', 'inverted.csv');

// コマンドライン引数処理
const args = process.argv.slice(2);

if (args[0] === 'build') {
  buildIndex(CORPUS_PATH, INDEX_PATH);
} else if (args[0] === 'search' && args[1]) {
  const query = args[1];
  try {
    console.log(`検索中: "${query}"`);
    const index = loadIndex(INDEX_PATH);
    const docs = readDocuments(CORPUS_PATH);
    const idf = calculateDF(docs);
    const results = search(query, index, idf);
    
    console.log('検索結果 (関連性でソート):');
    results.forEach((result, i) => {
      console.log(`${i + 1}. ${result.docId} (スコア: ${result.score.toFixed(6)})`);
    });
  } catch (error) {
    console.error('検索に失敗しました:', error);
  }
} else {
  console.log('使用法:');
  console.log('  インデックスの構築: node run.js build');
  console.log('  検索: node run.js search "query terms"');
}

機能のテストと検証

テストデータの準備

corpus ディレクトリに 3 つの英語ドキュメントを作成します。

ai.txt: "Artificial intelligence is the simulation of human intelligence processes by machines, especially computer systems. These processes include learning, reasoning, and self-correction."
ml.txt: "Machine learning is a subset of artificial intelligence focused on developing algorithms that learn from data. It enables computers to improve performance on a task through experience."
dl.txt: "Deep learning is a type of machine learning based on artificial neural networks with multiple layers. It excels at processing unstructured data like images and text."

インデックス構築テスト

node run.js build を実行すると、コンソールに処理プロセスが出力され、完了後、index/inverted.csv は次のコンテンツを生成します (抜粋)。

term,documents
"intelligence",ai.txt:0.057538;ml.txt:0.028769
"artificial",ai.txt:0.057538;dl.txt:0.038359
"machine",ai.txt:0.028769;ml.txt:0.028769;dl.txt:0.025573
"learning",ml.txt:0.057538;dl.txt:0.057538

検索機能テスト

node run.js search "machine learning" を実行すると、次のようになります。

検索中: "machine learning"
検索結果 (関連性でソート):
1. ml.txt (スコア: 0.003308)
2. dl.txt (スコア: 0.001462)
3. ai.txt (スコア: 0.000832)

結果は予想どおりです: ml.txt (機械学習) が最も関連性が高く、次に dl.txt (深層学習)、ai.txt (人工知能) の関連性が最も低くなっています。

技術的な最適化と拡張の方向性

基本バージョンの制限事項

現在の実装には明らかな制限事項があります。

簡単なトークン化: スペースで分割するだけで、ハイフンで結合された単語 (例: "state-of-the-art")、省略形 (例: "don't") などを処理しません。
インデックス効率が低い: CSV 形式では、クエリ中にフルテキストスキャンが必要となり、大規模なデータセットではパフォーマンスが低下します。
基本的なランキングアルゴリズム: 単純な重み付けの合計のみを使用し、コサイン類似度などのより正確なアルゴリズムを実装していません。
ストップワード処理なし: "the" や "is" などの高頻度の意味のない単語がインデックススペースを占有します。

最適化の実装計画

1. 高度なトークン化実装

特別なケースを処理するために、トークン化機能を改善します。

function advancedTokenize(text) {
  let cleaned = cleanText(text);
  // ハイフンと省略形を処理
  cleaned = cleaned.replace(/-/g, ' ').replace(/'s/g, ' ');
  return cleaned.split(' ').filter(token => token.length > 1); // 1 文字のトークンをフィルタリング
}

2. ストップワードのフィルタリング

ストップワードリストを追加してフィルタリングします。

const STOP_WORDS = new Set([
  'the', 'and', 'of', 'to', 'a', 'in', 'is', 'it', 'you', 'that'
  // より多くのストップワードで拡張できます
]);

function tokenizeWithStopWords(text) {
  return advancedTokenize(text).filter(token => !STOP_WORDS.has(token));
}

3. インデックス形式の最適化

CSV をより効率的なキーと値のストレージ (例: term|docId|docId (行ごと)) に変更して、解析を高速化します。

// 最適化されたインデックス形式の生成
function buildOptimizedIndex(docVectors) {
  let indexContent = '';
  for (const term in index) {
    const docsStr = index[term]
      .map(item => `${item.docId}:${item.weight.toFixed(6)}`)
      .join('|');
    indexContent += `${term}|${docsStr}\n`;
  }
  return indexContent;
}

4. コサイン類似性ランキング

より正確な類似性計算を実装します。

function calculateCosineSimilarity(queryVector, docVector) {
  let dotProduct = 0;
  let queryNorm = 0;
  let docNorm = 0;
  
  // ドット積とベクトルの大きさを計算
  for (const term in queryVector) {
    queryNorm += Math.pow(queryVector[term], 2);
    if (docVector[term]) {
      dotProduct += queryVector[term] * docVector[term];
    }
  }
  
  for (const term in docVector) {
    docNorm += Math.pow(docVector[term], 2);
  }
  
  // 0 除算を防ぐ
  if (queryNorm === 0 || docNorm === 0) return 0;
  
  return dotProduct / (Math.sqrt(queryNorm) * Math.sqrt(docNorm));
}

技術概要と応用シナリオ

この記事で実装した検索エンジンは簡単なものですが、最新の検索エンジンのコアコンポーネント（テキスト処理、TF-IDF 重み付け、逆インデックス、結果のランキング）がすべて含まれています。ピュア Node.js で実装することで、外部ライブラリへの依存関係を回避し、各技術リンクの実装の詳細を深く理解できます。

この技術は、以下に応用できます。

小規模ドキュメントライブラリの検索: プロジェクトドキュメントやヘルプシステムの内部検索など
教育デモンストレーション: 情報検索の核心的な原則を直感的に示す
2 次開発の基礎: 中国語の単語分割 (ICU ライブラリまたはカスタム分割の追加が必要)、分散インデックス、その他のより複雑なシステムをサポートするように拡張できます

技術的な進化の観点から見ると、TF-IDF は、BM25 などのより高度なアルゴリズムの基礎であり、CSV インデックスは、Lucene などのプロフェッショナルなインデックスライブラリの簡略化されたバージョンと見なすことができます。これらの基本的な実装を理解することで、開発者は Elasticsearch などの高度なツールの動作原理をより深く理解できます。