Aufbau einer englischen Suchmaschine mit TF-IDF unter Verwendung von reinem Node.js: Von den Prinzipien zur CSV-Inverted-Index-Implementierung

Im Zeitalter der Informationsexplosion sind Suchmaschinen zum zentralen Werkzeug für den Zugriff auf Informationen geworden. Von Google bis Bing basieren diese großen Suchmaschinen auf komplexen technischen Architekturen, aber ihre Kernprinzipien können mit grundlegenden Technologie-Stacks implementiert werden. Dieser Artikel führt Sie durch den Aufbau einer TF-IDF-Algorithmus-basierten englischen Suchmaschine von Grund auf mit reinem Node.js, ohne Bibliotheken von Drittanbietern, wobei der invertierte Index in CSV-Dateien gespeichert wird. Durch diese Übung erhalten Sie ein tiefes Verständnis der Kernmechanismen der Informationsbeschaffung und beherrschen Schlüsseltechnologien in den Bereichen Textverarbeitung, Gewichtungsberechnung und Indexkonstruktion.

Grundlagen von Suchmaschinen und TF-IDF

Eine Suchmaschine ist im Wesentlichen ein Informationsfiltersystem, dessen Kernfunktion darin besteht, Benutzeranfragen entgegenzunehmen, schnell die relevantesten Ergebnisse aus massiven Dokumenten zu finden und diese zu ordnen. Moderne Suchmaschinen bestehen aus vier Kernmodulen: Crawler (Datenerfassung), Indexer (Aufbau von Retrieval-Strukturen), Retriever (Anfrageverarbeitung) und Ranking-Algorithmus (Ergebnisoptimierung). Unsere vereinfachte Version konzentriert sich auf den Indexer und den Retriever, wobei lokale Dokumente als Datenquelle verwendet werden.

TF-IDF (Term Frequency-Inverse Document Frequency) ist ein klassischer Gewichtungsalgorithmus im Bereich des Information Retrieval, der 1972 von Karen Spärck Jones vorgeschlagen wurde und in verschiedenen Textsystemen immer noch weit verbreitet ist. Die Kernidee ist: Die Bedeutung eines Wortes für ein Dokument ist proportional zu seiner Häufigkeit des Vorkommens in dem Dokument und umgekehrt proportional zu seiner Häufigkeit des Vorkommens in allen Dokumenten.

• Term Frequency (TF): Die Anzahl, wie oft ein Wort im aktuellen Dokument vorkommt, geteilt durch die Gesamtzahl der Wörter im Dokument. Die Formel lautet TF(t,d) = count(t,d) / totalTerms(d). Wenn beispielsweise "machine" 5 Mal in einem Dokument mit insgesamt 100 Wörtern vorkommt, beträgt der TF-Wert 0,05.

• Inverse Document Frequency (IDF): Der Logarithmus des Kehrwerts der Anzahl der Dokumente, die das Wort enthalten. Die Formel lautet IDF(t) = log(totalDocs / docsWithTerm(t)). Wenn der Korpus 1000 Dokumente enthält, von denen 20 "learning" enthalten, beträgt der IDF-Wert log(1000/20) = log(50) ≈ 3,912.

Die Multiplikation der beiden ergibt TF-IDF(t,d) = TF(t,d) × IDF(t). Je höher dieser Wert, desto repräsentativer ist das Wort für das aktuelle Dokument. Während der Suche kann durch die Berechnung der TF-IDF-Vektorähnlichkeit (wie z. B. der Kosinusähnlichkeit) zwischen den Suchbegriffen und Dokumenten eine Ergebnisreihenfolge erreicht werden.

Implementierungsschritte mit reinem Node.js

Umgebungsvorbereitung und Projektstruktur

Dieses Projekt basiert nur auf der Node.js-Runtime (v14+ ist ausreichend) und erfordert keine Installation von npm-Paketen. Erstellen Sie die folgende Verzeichnisstruktur:

tfidf-search/
├── corpus/         # Speichert englische Dokumente
│   ├── doc1.txt
│   ├── doc2.txt
│   └── ...
├── index/          # Speichert Indexdateien
│   └── inverted.csv
├── src/
│   ├── indexer.js  # Indexkonstruktionsprogramm
│   └── searcher.js # Suchprogramm
└── run.js          # Einstiegsdatei

Das Verzeichnis corpus speichert englische Dokumente, die durchsucht werden sollen, das Verzeichnis index wird zum Speichern von CSV-Dateien des invertierten Index verwendet und src enthält den Kernimplementierungscode.

1. Textdatenverarbeitung

Die Textverarbeitung ist die Grundlage einer Suchmaschine und erfordert das Lesen, Bereinigen und Tokenisieren von Dokumenten. Erstellen Sie src/indexer.js und implementieren Sie grundlegende Verarbeitungsfunktionen:

// Dokumentinhalt lesen
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;
}

Die Textbereinigung umfasst das Entfernen von Satzzeichen, die Konvertierung in Kleinbuchstaben und die Tokenisierung. Die englische Tokenisierung ist relativ einfach und kann durch Aufteilen nach Leerzeichen erfolgen, es müssen jedoch Sonderfälle behandelt werden:

function cleanText(text) {
  // Entfernen Sie alle HTML-Tags
  let cleaned = text.replace(/<[^>]*>/g, ' ');
  // In Kleinbuchstaben umwandeln
  cleaned = cleaned.toLowerCase();
  // Satzzeichen und Sonderzeichen entfernen
  cleaned = cleaned.replace(/[^a-z0-9\s]/g, ' ');
  // Mehrere Leerzeichen zu einem zusammenfügen
  cleaned = cleaned.replace(/\s+/g, ' ').trim();
  return cleaned;
}

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

2. TF-IDF-Berechnungsimplementierung

Term Frequency (TF) Berechnung

Die TF-Berechnung muss die Häufigkeit jedes Wortes im Dokument zählen, implementiert wie folgt:

function calculateTF(tokens) {
  const tf = {};
  const totalTerms = tokens.length;
  
  for (const token of tokens) {
    if (token) { // Leere Zeichenketten überspringen
      tf[token] = (tf[token] || 0) + 1;
    }
  }
  
  // In Häufigkeit umwandeln (Anzahl der Wörter / Gesamtzahl der Wörter)
  for (const term in tf) {
    tf[term] = tf[term] / totalTerms;
  }
  
  return tf;
}

Inverse Document Frequency (IDF) Berechnung

IDF erfordert zunächst das Zählen der Anzahl der Dokumente, die jedes Wort enthalten:

function calculateDF(docs) {
  const df = {};
  const totalDocs = docs.length;
  
  for (const doc of docs) {
    const tokens = new Set(tokenize(doc.content)); // Deduplizierung
    for (const token of tokens) {
      if (token) {
        df[token] = (df[token] || 0) + 1;
      }
    }
  }
  
  // IDF berechnen: log(Gesamtzahl der Dokumente / Anzahl der Dokumente, die den Begriff enthalten)
  const idf = {};
  for (const term in df) {
    idf[term] = Math.log(totalDocs / df[term]);
  }
  
  return idf;
}

Dokumentvektorgenerierung

Kombinieren Sie TF und IDF, um Vektoren für jedes Dokument zu generieren:

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. Invertierte Indexkonstruktion und CSV-Speicherung

Der invertierte Index ist die Kerndatenstruktur einer Suchmaschine, die die Zuordnung zwischen Begriffen und der Liste der Dokumente speichert, die den Begriff zusammen mit ihren Gewichtungen enthalten. Seine Struktur ist in der Regel: Begriff,docId1,docId2,...

function buildInvertedIndex(docVectors) {
  const index = {};
  
  // In-Memory-Invertierten Index erstellen
  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]
      });
    }
  }
  
  // In CSV-Format konvertieren
  let csvContent = 'Begriff,Dokumente\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;
}

// Index in CSV-Datei speichern
function saveIndex(csvContent, indexPath) {
  fs.writeFileSync(indexPath, csvContent, 'utf8');
}

Die Gründe für die Wahl des CSV-Formats sind: starke Lesbarkeit von reinem Text, einfache Implementierung (keine Serialisierungsbibliotheken erforderlich) und direkte Analyse durch Tools wie Excel. Der Nachteil ist jedoch, dass während der Abfragen eine Volltextsuche erforderlich ist, die später zu effizienteren Formaten optimiert werden kann.

4. Vollständiger Indexkonstruktionsprozess

Integrieren Sie die obigen Funktionen in den Indexkonstruktionsprozess:

async function buildIndex(corpusPath, indexPath) {
  try {
    console.log('Dokumente lesen...');
    const docs = readDocuments(corpusPath);
    
    console.log('Dokumentfrequenz (DF) berechnen...');
    const idf = calculateDF(docs);
    
    console.log('Dokumentvektoren generieren...');
    const docVectors = generateDocVectors(docs, idf);
    
    console.log('Invertierten Index erstellen...');
    const csvContent = buildInvertedIndex(docVectors);
    
    console.log('Index in CSV speichern...');
    saveIndex(csvContent, indexPath);
    
    console.log(`Indexkonstruktion abgeschlossen, ${docs.length} Dokumente verarbeitet`);
  } catch (error) {
    console.error('Indexkonstruktion fehlgeschlagen:', error);
  }
}

module.exports = { buildIndex };

5. Suchfunktionsimplementierung

Das Suchprogramm muss: den Index laden, die Abfrage analysieren, die Ähnlichkeit berechnen und Ergebnisse zurückgeben.

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

// CSV-Index laden und in In-Memory-Objekt konvertieren
function loadIndex(indexPath) {
  const index = {};
  const csvContent = fs.readFileSync(indexPath, 'utf8');
  const lines = csvContent.split('\n');
  
  // Kopfzeile überspringen
  for (let i = 1; i < lines.length; i++) {
    const line = lines[i].trim();
    if (!line) continue;
    
    // CSV-Zeile parsen (in Anführungszeichen gesetzte Fälle behandeln)
    const [termPart, docsPart] = line.split(',');
    const term = termPart.replace(/"/g, ''); // Anführungszeichen entfernen
    
    if (docsPart) {
      index[term] = docsPart.split(';').map(item => {
        const [docId, weight] = item.split(':');
        return { docId, weight: parseFloat(weight) };
      });
    }
  }
  
  return index;
}

// Abfragevektor berechnen
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;
}

// Suche ausführen
function search(query, index, idf) {
  const queryVector = getQueryVector(query, idf);
  const results = {};
  
  // Dokumentpunktzahl akkumulieren
  for (const term in queryVector) {
    if (index[term]) {
      const queryWeight = queryVector[term];
      for (const doc of index[term]) {
        // Einfache Ähnlichkeitsberechnung: Summe der Gewichtsprodukte
        const score = (results[doc.docId] || 0) + (queryWeight * doc.weight);
        results[doc.docId] = score;
      }
    }
  }
  
  // In sortiertes Array konvertieren
  return Object.entries(results)
    .map(([docId, score]) => ({ docId, score }))
    .sort((a, b) => b.score - a.score);
}

module.exports = { loadIndex, search };

6. Einstiegsprogramm-Implementierung

Erstellen Sie run.js als Programmeinstieg, der zwei Modi unterstützt: Indexkonstruktion und Suche:

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');

// Befehlszeilenargumentverarbeitung
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(`Suche: "${query}"`);
    const index = loadIndex(INDEX_PATH);
    const docs = readDocuments(CORPUS_PATH);
    const idf = calculateDF(docs);
    const results = search(query, index, idf);
    
    console.log('Suchergebnisse (sortiert nach Relevanz):');
    results.forEach((result, i) => {
      console.log(`${i + 1}. ${result.docId} (Score: ${result.score.toFixed(6)})`);
    });
  } catch (error) {
    console.error('Suche fehlgeschlagen:', error);
  }
} else {
  console.log('Verwendung:');
  console.log('  Index erstellen: node run.js build');
  console.log('  Suche: node run.js search "Suchbegriffe"');
}

Funktionstests und Überprüfung

Testdatenvorbereitung

Erstellen Sie 3 englische Dokumente im Verzeichnis corpus:

• 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."

Indexkonstruktionstest

Führen Sie node run.js build aus, die Konsole gibt den Verarbeitungsprozess aus, und nach Abschluss wird index/inverted.csv wie folgt generiert (Auszug):

Begriff,Dokumente
"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

Suchfunktionstest

Führen Sie node run.js search "machine learning" aus, was Folgendes zurückgeben sollte:

Suche: "machine learning"
Suchergebnisse (sortiert nach Relevanz):
1. ml.txt (Score: 0.003308)
2. dl.txt (Score: 0.001462)
3. ai.txt (Score: 0.000832)

Die Ergebnisse sind wie erwartet: ml.txt (Machine Learning) ist am relevantesten, gefolgt von dl.txt (Deep Learning), und ai.txt (Artificial Intelligence) hat die geringste Relevanz.

Technische Optimierung und Erweiterungsrichtungen

Einschränkungen der Basisversion

Die aktuelle Implementierung hat offensichtliche Einschränkungen:

• Einfache Tokenisierung: Teilt nur nach Leerzeichen, behandelt keine Wörter mit Bindestrich (z. B. "State-of-the-Art"), Abkürzungen (z. B. "Don't") usw.
• Geringe Indexeffizienz: Das CSV-Format erfordert während der Abfragen eine Volltextsuche, mit Leistungsverschlechterung bei großen Datensätzen.
• Grundlegender Ranking-Algorithmus: Verwendet nur eine einfache gewichtete Summierung, ohne genauere Algorithmen wie die Kosinusähnlichkeit zu implementieren.
• Keine Stoppwortverarbeitung: Häufige, bedeutungslose Wörter wie "The" und "Is" belegen Indexspeicherplatz.

Optimierungs-Implementierungspläne

1. Erweiterte Tokenisierungs-Implementierung

Verbessern Sie die Tokenisierungsfunktion, um Sonderfälle zu behandeln:

function advancedTokenize(text) {
  let cleaned = cleanText(text);
  // Bindestriche und Abkürzungen behandeln
  cleaned = cleaned.replace(/-/g, ' ').replace(/'s/g, ' ');
  return cleaned.split(' ').filter(token => token.length > 1); // Einzelzeichen-Token filtern
}

2. Stoppwortfilterung

Fügen Sie eine Stoppwortliste hinzu und filtern Sie:

const STOP_WORDS = new Set([
  'the', 'and', 'of', 'to', 'a', 'in', 'is', 'it', 'you', 'that'
  // Kann mit weiteren Stoppwörtern erweitert werden
]);

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

3. Indexformatoptimierung

Ändern Sie CSV in eine effizientere Schlüssel-Wert-Speicherung (z. B. Begriff|DocId|DocId pro Zeile), um die Analyse zu beschleunigen:

// Optimierte Indexformaterstellung
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. Kosinusähnlichkeits-Ranking

Implementieren Sie eine genauere Ähnlichkeitsberechnung:

function calculateCosineSimilarity(queryVector, docVector) {
  let dotProduct = 0;
  let queryNorm = 0;
  let docNorm = 0;
  
  // Berechnen Sie das Punktprodukt und die Vektorgrößen
  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);
  }
  
  // Division durch Null verhindern
  if (queryNorm === 0 || docNorm === 0) return 0;
  
  return dotProduct / (Math.sqrt(queryNorm) * Math.sqrt(docNorm));
}

Technische Zusammenfassung und Anwendungsszenarien

Obwohl die in diesem Artikel implementierte Suchmaschine einfach ist, enthält sie vollständig die Kernkomponenten moderner Suchmaschinen: Textverarbeitung, TF-IDF-Gewichtung, invertierte Indizierung und Ergebnis-Ranking. Durch die Implementierung mit reinem Node.js vermeiden wir Abhängigkeiten von externen Bibliotheken und gewinnen ein tiefes Verständnis der Implementierungsdetails jeder technischen Verbindung.

Diese Technologie kann angewendet werden in:

• Kleine Dokumentbibliotheksuche: wie z. B. interne Suche nach Projektdokumenten und Hilfesystemen
• Lehrdemonstrationen: anschauliche Darstellung der Kernprinzipien der Informationsbeschaffung
• Sekundäre Entwicklungsgrundlage: kann erweitert werden, um die chinesische Wortsegmentierung zu unterstützen (erfordert das Hinzufügen der ICU-Bibliothek oder eine benutzerdefinierte Segmentierung), die verteilte Indizierung und andere komplexere Systeme

Aus technischer Sicht ist TF-IDF die Grundlage für fortschrittlichere Algorithmen wie BM25, und die CSV-Indizierung kann als vereinfachte Version professioneller Indizierungsbibliotheken wie Lucene angesehen werden. Das Verständnis dieser grundlegenden Implementierungen kann Entwicklern helfen, die Funktionsprinzipien fortgeschrittener Tools wie Elasticsearch besser zu verstehen.

Leapcell: Das Beste von Serverless Web Hosting

Abschließend empfehlen wir die am besten geeignete Plattform für die Bereitstellung von Node.js-Diensten: Leapcell

🚀 Entwickeln Sie mit Ihrer Lieblingssprache

Entwickeln Sie mühelos in JavaScript, Python, Go oder Rust.

🌍 Stellen Sie unbegrenzt Projekte kostenlos bereit

Zahlen Sie nur für das, was Sie nutzen – keine Anfragen, keine Gebühren.

⚡ Pay-as-You-Go, keine versteckten Kosten

Keine Leerlaufgebühren, nur nahtlose Skalierbarkeit.

📖 Entdecken Sie unsere Dokumentation

🔹 Folgen Sie uns auf Twitter: @LeapcellHQ