Implementierung einer TF-IDF-basierten englischen Suchmaschine in reinem Python: Aufbau eines abhängigkeitsfreien Retrieval-Systems von Grund auf

Im heutigen Zeitalter der Informationsflut sind Suchmaschinen zur wichtigsten Möglichkeit für Menschen geworden, auf Informationen zuzugreifen. Während kommerzielle Suchmaschinen wie Google und Bing komplexe technische Architekturen im Hintergrund haben, können ihre Kernprinzipien durch grundlegende Information-Retrieval-Technologien verstanden werden. Dieser Artikel führt Sie durch den Aufbau einer TF-IDF-Algorithmus-basierten englischen Suchmaschine von Grund auf, wobei nur die Python-Standardbibliothek ohne Abhängigkeiten von Drittanbietern verwendet und die wichtige invertierte Indexstruktur im CSV-Format gespeichert wird. Durch diese Übung erhalten Sie ein tiefes Verständnis dafür, wie Suchmaschinen funktionieren, und beherrschen Kerntechnologien in den Bereichen Textverarbeitung, Indexkonstruktion und Relevanzberechnung.

Kernkomponenten einer Suchmaschine

Eine vollständige Suchmaschine besteht typischerweise aus vier Kernmodulen: Dokumentverarbeitungsmodul, Indexkonstruktionsmodul, Anfrageverarbeitungsmodul und Ranking-Modul. Im Gegensatz zu Implementierungen, die auf Bibliotheken von Drittanbietern basieren, erfordert eine reine Python-Implementierung, dass wir die Details jedes环节 manuell behandeln, was ein tieferes Verständnis der Prinzipien hinter jedem Schritt ermöglicht.

Das Dokumentverarbeitungsmodul konvertiert Rohdaten in strukturierte Daten, die für die Berechnung geeignet sind, einschließlich Operationen wie Tokenisierung, Rauschentfernung (z. B. Interpunktion) und Normalisierung (z. B. Fallkonvertierung). Das Indexkonstruktionsmodul ist der Kern der Suchmaschine, der durch den Aufbau eines invertierten Indexes schnelle Abfragen ermöglicht, der aufzeichnet, in welchen Dokumenten jeder Begriff vorkommt und wo sie sich befinden. Das Anfrageverarbeitungsmodul empfängt Benutzereingabeabfragen und führt die gleichen Normalisierungsoperationen wie die Dokumentverarbeitung durch, um Begriffe im Index abzugleichen. Das Ranking-Modul berechnet den Relevanzwert zwischen den Abfragebegriffen und jedem Dokument mithilfe des TF-IDF-Algorithmus und gibt die Ergebnisse nach Wert sortiert zurück.

Prinzipien des TF-IDF-Algorithmus

TF-IDF (Term Frequency-Inverse Document Frequency) ist eine statistische Methode zur Bewertung der Bedeutung eines Begriffs in einer Dokumentsammlung. Seine Kernidee ist: Die Bedeutung eines Begriffs ist proportional zu seiner Häufigkeit in einem bestimmten Dokument und umgekehrt proportional zu seiner Häufigkeit in der gesamten Dokumentsammlung.

Berechnung der Termfrequenz (TF)

Die Termfrequenz bezieht sich auf die Anzahl der Vorkommnisse eines Begriffs in einem bestimmten Dokument. Um den Einfluss der Dokumentlänge auf die Ergebnisse zu vermeiden, wird normalerweise eine Normalisierung angewendet:

TF(t,d) = Anzahl der Vorkommnisse des Begriffs t im Dokument d / Gesamtzahl der Begriffe im Dokument d

Wenn beispielsweise in einem Dokument mit 100 Begriffen „Lernen“ 5 Mal vorkommt, beträgt seine Termfrequenz 5/100 = 0,05.

Berechnung der inversen Dokumentfrequenz (IDF)

Die inverse Dokumentfrequenz misst die Unterscheidungskraft eines Begriffs, berechnet als:

IDF(t) = log(Gesamtzahl der Dokumente / Anzahl der Dokumente, die den Begriff t enthalten)

Wenn ein Begriff in den meisten Dokumenten vorkommt, ist sein IDF-Wert niedrig, was auf eine schwache Unterscheidungskraft hindeutet; umgekehrt, wenn ein Begriff nur in wenigen Dokumenten vorkommt, ist sein IDF-Wert hoch, was auf eine starke Unterscheidungskraft hindeutet. Wenn beispielsweise angenommen wird, dass es insgesamt 10 Dokumente gibt und „Maschine“ in 3 davon vorkommt, beträgt sein IDF-Wert log(10/3) ≈ 1,20397.

Berechnung des TF-IDF-Werts

Der TF-IDF-Wert ist das Produkt aus Termfrequenz und inverser Dokumentfrequenz:

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

Dieser Wert spiegelt umfassend die Bedeutung des Begriffs t im Dokument d wider und ist ein wichtiger Indikator zur Messung der Relevanz zwischen einem Dokument und einer Abfrage.

Design des invertierten Indexes

Der invertierte Index ist eine wichtige Datenstruktur für schnelle Abfragen in Suchmaschinen, die jeden Begriff und die Dokumente und Positionen aufzeichnet, in denen er vorkommt. In einer reinen Python-Implementierung müssen wir eine vernünftige invertierte Indexstruktur entwerfen und diese zur Persistenz im CSV-Format ablegen.

Die grundlegende Struktur eines invertierten Indexes umfasst drei Teile: Begriff, Dokument-ID (doc_id) und Positionen. Die Positionsinformationen zeichnen die spezifischen Orte auf, an denen der Begriff im Dokument vorkommt, und erleichtern so nachfolgende Phrasenabfragen und Nachbarschaftsabfragen.

Das CSV-Dateiformat ist wie folgt aufgebaut:

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

Dieses Format ermöglicht uns, das Standard-csv-Modul von Python für Lese- und Schreibvorgänge zu verwenden. Jedes Vorkommen eines Begriffs in verschiedenen Dokumenten wird als Zeile erfasst, wobei das Feld Positionen die Positionsliste als Zeichenkette speichert.

Schritte zur reinen Python-Implementierung

Als Nächstes werden wir im Detail beschreiben, wie man eine TF-IDF-basierte englische Suchmaschine von Grund auf mit reinem Python implementiert, einschließlich Dokumentvorverarbeitung, Erstellung des invertierten Indexes, TF-IDF-Berechnung, Abfrageverarbeitung und Ergebnisranking.

Schritt 1: Dokumentvorverarbeitung

Die Dokumentvorverarbeitung konvertiert reinen Text in strukturierte Daten, hauptsächlich einschließlich der folgenden Operationen:

• Fallkonvertierung: Konvertieren Sie den gesamten Text in Kleinbuchstaben, um zu vermeiden, dass „Machine“ und „machine“ als unterschiedliche Begriffe behandelt werden.
• Entfernung von Interpunktionszeichen: Entfernen Sie Interpunktionszeichen aus dem Text, um Rauschen zu reduzieren.
• Tokenisierung: Teilen Sie fortlaufenden Text in einzelne Begriffe auf.
• Stoppwort-Entfernung: Filtern Sie hochfrequente Wörter ohne praktische Bedeutung wie „the“ und „and“ heraus.
• Einfaches Stemming: Reduzieren Sie die Begriffe auf ihre Grundform (vereinfachte Implementierung).

Hier ist der Implementierungscode:

import string

# Definieren Sie ein englisches Stoppwort-Set
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 vorverarbeiten: Fallkonvertierung, Entfernung von Interpunktionszeichen, Tokenisierung, Entfernung von Stoppwörtern"""
    # In Kleinbuchstaben konvertieren
    text = text.lower()
    
    # Interpunktionszeichen entfernen
    translator = str.maketrans('', '', string.punctuation)
    text = text.translate(translator)
    
    # Tokenisierung (einfache Leerzeichenaufteilung; in praktischen Anwendungen kann komplexere Logik verwendet werden)
    tokens = text.split()
    
    # Stoppwörter und leere Zeichenketten entfernen
    tokens = [token for token in tokens if token not in STOP_WORDS and token.strip() != '']
    
    # Einfaches Stemming (vereinfachte Version)
    tokens = [stem_token(token) for token in tokens]
    
    return tokens

def stem_token(token):
    """Einfache Stemming-Funktion (in praktischen Anwendungen können komplexere Algorithmen verwendet werden)"""
    # Häufige Suffixe behandeln
    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

# Testen Sie die Vorverarbeitungsfunktion
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("Vorverarbeitete Begriffe:", processed_tokens)

Diese Vorverarbeitungsfunktion implementiert grundlegende Textbereinigung und -normalisierung und legt damit den Grundstein für die nachfolgende Indexkonstruktion und TF-IDF-Berechnung. Es ist zu beachten, dass die Tokenisierung und das Stemming hier vereinfachte Implementierungen sind; in praktischen Anwendungen können komplexere Algorithmen verwendet werden, um die Genauigkeit zu verbessern.

Schritt 2: Erstellen Sie einen invertierten Index und speichern Sie ihn als CSV

Der Prozess des Erstellens eines invertierten Indexes umfasst das Durchlaufen aller Dokumente, das Aufzeichnen der Dokument-IDs und Positionsinformationen, in denen jeder Begriff vorkommt, und das Speichern der Ergebnisse als CSV-Datei.

import csv
from collections import defaultdict

def build_inverted_index(documents):
    """Invertierten Index erstellen und als CSV-Datei speichern"""
    inverted_index = defaultdict(list)  # Struktur: {Begriff: [(doc_id, Positionen), ...]}
    
    for doc_id, doc in enumerate(documents):
        # Dokument vorverarbeiten
        tokens = preprocess_text(doc)
        
        # Positionen jedes Begriffs im aktuellen Dokument aufzeichnen
        term_positions = defaultdict(list)
        for pos, term in enumerate(tokens):
            term_positions[term].append(pos)
        
        # Invertierten Index aktualisieren
        for term, positions in term_positions.items():
            inverted_index[term].append((doc_id, positions))
    
    # Invertierten Index als CSV-Datei speichern
    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:
                # Positionsliste zur Speicherung in Zeichenkette konvertieren
                positions_str = str(positions)
                writer.writerow([term, doc_id, positions_str])
    
    return inverted_index

# Beispieldokumentsammlung
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."
]

# Invertierten Index erstellen
inverted_index = build_inverted_index(documents)
print(f"Invertierter Index erstellt, enthält {len(inverted_index)} Begriffe")

Dieser Code durchläuft zuerst jedes Dokument, verarbeitet es vor, zeichnet die Positionen jedes Begriffs im Dokument auf, organisiert diese Informationen in einem invertierten Index und speichert sie als CSV-Datei. Der invertierte Index ist als Dictionary aufgebaut, wobei die Schlüssel Begriffe und die Werte Listen von Tupeln sind, die Dokument-IDs und Positionslisten enthalten.

Schritt 3: TF-IDF-Werte berechnen

Zum Berechnen von TF-IDF-Werten müssen zunächst die Termfrequenzen und inversen Dokumentfrequenzen gezählt werden, dann ihr Produkt berechnet werden. In einer reinen Python-Implementierung müssen wir diese Berechnungen manuell durchführen.

import math  # Importieren Sie die Mathematikbibliothek für die Logarithmusberechnung

def calculate_tfidf(documents, inverted_index):
    """TF-IDF-Werte für jeden Begriff in jedem Dokument berechnen"""
    num_docs = len(documents)
    tfidf = {}  # Struktur: {doc_id: {Begriff: tfidf_value, ...}, ...}
    
    # Gesamtzahl der Begriffe für jedes Dokument berechnen
    doc_lengths = []
    for doc in documents:
        tokens = preprocess_text(doc)
        doc_lengths.append(len(tokens))
    
    # Dokumentfrequenz für jeden Begriff berechnen (Anzahl der Dokumente, die den Begriff enthalten)
    doc_freq = {term: len(entries) for term, entries in inverted_index.items()}
    
    # TF-IDF berechnen
    for term, entries in inverted_index.items():
        # IDF berechnen
        idf = math.log(num_docs / (doc_freq[term] + 1))  # +1, um eine Division durch Null zu vermeiden
        
        for doc_id, positions in entries:
            # TF berechnen
            tf = len(positions) / doc_lengths[doc_id] if doc_lengths[doc_id] > 0 else 0
            
            # TF-IDF berechnen
            tfidf_value = tf * idf
            
            # Ergebnisse speichern
            if doc_id not in tfidf:
                tfidf[doc_id] = {}
            tfidf[doc_id][term] = tfidf_value
    
    return tfidf

# TF-IDF-Werte berechnen
tfidf_scores = calculate_tfidf(documents, inverted_index)
print("TF-IDF-Berechnung abgeschlossen")

Dieser Code berechnet zunächst die Länge jedes Dokuments (Gesamtzahl der Begriffe nach der Vorverarbeitung) und die Dokumentfrequenz jedes Begriffs, berechnet dann jeweils die Termfrequenz und die inverse Dokumentfrequenz und berechnet schließlich ihr Produkt, um den TF-IDF-Wert zu erhalten. Die Berechnungsergebnisse werden zur einfachen Verwendung in nachfolgenden Abfragen in einem verschachtelten Wörterbuch gespeichert.

Schritt 4: Abfragen verarbeiten und Ergebnisse zurückgeben

Das Abfrageverarbeitungsmodul muss Benutzereingabeabfragen vorverarbeiten, Dokumente, die die Abfragebegriffe enthalten, basierend auf dem invertierten Index finden, den Relevanzwert zwischen der Abfrage und jedem Dokument berechnen und die Ergebnisse nach Wert sortiert zurückgeben.

import math  # Stellen Sie sicher, dass die Mathematikbibliothek importiert ist

def search(query, documents, inverted_index, tfidf_scores, top_n=3):
    """Abfrage verarbeiten und relevanteste Dokumente zurückgeben"""
    # Abfrage vorverarbeiten
    query_terms = preprocess_text(query)
    if not query_terms:
        return []
    
    # Dokumente abrufen, die mindestens einen Abfragebegriff enthalten
    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)
    
    # Relevanzwerte zwischen Abfrage und jedem relevanten Dokument berechnen
    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]
        
        # Wert normalisieren (durch Anzahl der Abfragebegriffe dividieren)
        score /= len(query_terms)
        scores.append((doc_id, score))
    
    # Nach Wert sortieren
    scores.sort(key=lambda x: x[1], reverse=True)
    
    # Top-N-Ergebnisse zurückgeben
    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

# Suchfunktionen testen
query = "machine learning"
results = search(query, documents, inverted_index, tfidf_scores)
print(f"Abfrage: {query}")
for i, result in enumerate(results, 1):
    print(f"\n Ergebnis {i} (Wert: {result['score']:.4f}):")
    print(result['document'])

Dieser Code verarbeitet zuerst die Abfragebegriffe vor, findet dann alle Dokumente, die die Abfragebegriffe enthalten, berechnet den Relevanzwert zwischen jedem Dokument und der Abfrage (hier wird eine einfache Summierungsmethode verwendet) und gibt schließlich die Ergebnisse nach Wert sortiert zurück.

Schritt 5: Invertierten Index aus CSV laden

Zur Persistenz müssen wir in der Lage sein, den invertierten Index aus einer CSV-Datei zu laden.

import csv
from collections import defaultdict

def load_inverted_index_from_csv(filename):
    """Invertierten Index aus CSV-Datei laden"""
    inverted_index = defaultdict(list)
    
    with open(filename, 'r', encoding='utf-8') as f:
        reader = csv.reader(f)
        next(reader)  # Kopfzeile überspringen
        
        for row in reader:
            term = row[0]
            doc_id = int(row[1])
            
            # Positionszeichenkette wieder in Liste konvertieren
            positions = eval(row[2])  # Hinweis: eval birgt Sicherheitsrisiken; sichere Methoden in praktischen Anwendungen verwenden
            
            inverted_index[term].append((doc_id, positions))
    
    return inverted_index

# Laden des invertierten Indexes testen
loaded_index = load_inverted_index_from_csv('inverted_index.csv')
print(f"Invertierter Index aus CSV geladen enthält {len(loaded_index)} Begriffe")

Dieser Code liest invertierte Indexdaten aus einer CSV-Datei, konvertiert die Positionsinformationen von einer Zeichenkette zurück in eine Liste und rekonstruiert die invertierte Indexstruktur. Es ist zu beachten, dass die Verwendung der eval-Funktion Sicherheitsrisiken birgt; in praktischen Anwendungen können sicherere Methoden (z. B. reguläre Ausdrucksanalyse) verwendet werden, um die Positionszeichenkette zu konvertieren.

Leistungsoptimierung und Erweiterung

Eine in reinem Python implementierte Suchmaschine kann bei der Verarbeitung umfangreicher Dokumente auf Leistungsprobleme stoßen. Hier sind einige Optimierungsvorschläge:

• Indexkomprimierung: Positionsinformationen im invertierten Index können mithilfe von Methoden wie der Delta-Codierung komprimiert werden, um Speicherplatz und Speichernutzung zu reduzieren.
• Caching-Mechanismus: Häufig aufgerufene Teile des Indexes im Speicher zwischenspeichern, um Festplatten-I/O-Operationen zu reduzieren.
• Paralleles Rechnen: Verwenden Sie das Multiprocessing-Modul von Python für paralleles Rechnen, wenn zeitaufwändige Operationen wie die TF-IDF-Berechnung durchgeführt werden.
• Abfrageoptimierung: Bei Abfragen mit mehreren Begriffen zuerst Dokumente finden, die alle Abfragebegriffe enthalten (Schnittmenge), bevor die Relevanz berechnet wird, um die Berechnung zu reduzieren.

Darüber hinaus kann die Funktionalität der Suchmaschine erweitert werden, um Phrasenabfragen, Nachbarschaftsabfragen, boolesche Abfragen usw. zu unterstützen, wodurch die Retrievalgenauigkeit und -flexibilität verbessert werden.

Herausforderungen in praktischen Anwendungen

In praktischen Anwendungen kann eine in reinem Python implementierte Suchmaschine mit den folgenden Herausforderungen konfrontiert sein:

• Leistungseinschränkungen: Im Vergleich zu kompilierten Sprachen wie C++ hat Python eine geringere Ausführungseffizienz und kann bei der Verarbeitung umfangreicher Daten Engpässe aufweisen.
• Funktionale Einschränkungen: Eine reine Python-Implementierung hat Probleme mit komplexen Aufgaben der Verarbeitung natürlicher Sprache wie der Auflösung von Wortbedeutungen und der Erkennung von Entitäten.
• Skalierbarkeit: Mit zunehmender Anzahl von Dokumenten und Vokabeln expandiert die Indexstruktur schnell, was komplexere verteilte Speicher- und Rechenarchitekturen erfordert.

Daher wird bei der tatsächlichen Entwicklung von Suchmaschinen die Benutzerfreundlichkeit von Python normalerweise mit den Vorteilen anderer Hochleistungssprachen kombiniert, um Systeme mit hybriden Architekturen zu erstellen.

Schlussfolgerung

In diesem Artikel habe wir eine TF-IDF-basierte englische Suchmaschine von Grund auf aufgebaut, ohne uns auf Bibliotheken von Drittanbietern zu verlassen, und den wichtigsten invertierten Index im CSV-Format gespeichert. Dieser Prozess hat es uns ermöglicht, ein tiefes Verständnis der Kernprinzipien und Implementierungsdetails von Suchmaschinen zu erlangen, einschließlich wichtiger Schritte wie der Dokumentvorverarbeitung, des Aufbaus des invertierten Indexes, der TF-IDF-Berechnung und der Abfrageverarbeitung.

Obwohl diese Implementierung relativ einfach ist, deckt sie den grundlegenden Rahmen moderner Suchmaschinen ab. Auf dieser Grundlage können Sie die Funktionalität weiter ausbauen und die Leistung optimieren, um ein leistungsfähigeres Retrieval-System aufzubauen. Ob für akademische Forschung oder praktische Anwendungen, das Verständnis dieser grundlegenden Prinzipien ist ein wichtiger Schritt, um Ihr Wissen über Information-Retrieval-Technologie zu vertiefen.

Wir hoffen, dass dieser Artikel Ihnen die Tür zum Bereich des Information Retrieval geöffnet hat und Ihr Interesse und Ihren Wunsch geweckt hat, die Suchmaschinentechnologie zu erkunden. In diesem Zeitalter der Informationsexplosion hilft uns die Beherrschung der Information-Retrieval-Technologie nicht nur, Informationen effizienter zu erhalten, sondern bietet auch eine solide Grundlage für die Forschung in Bereichen wie Data Mining und künstliche Intelligenz.

Leapcell: Das Beste von Serverless Webhosting

Schließlich empfehlen wir eine hervorragende Plattform für die Bereitstellung von Python-Diensten: Leapcell

🚀 Mit Ihrer Lieblingssprache entwickeln

Problemlos in JavaScript, Python, Go oder Rust entwickeln.

🌍 Unbegrenzt viele Projekte kostenlos bereitstellen

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