Der beste Weg, um mit dem ngram nach einem ähnlichen Dokument zu suchen

Ich habe eine Datenbank mit ungefähr 200 Dokumenten, deren Ngramme ich extrahiert habe. Ich möchte das Dokument in meiner Datenbank finden, das einem Abfragedokument am ähnlichsten ist. Mit anderen Worten, ich möchte das Dokument in der Datenbank finden, die die meisten ngramme mit dem Abfragedokument teilt. Im Moment kann ich jeden einzelnen durchgehen und einzeln vergleichen, aber dies nimmt O (N) Zeit in Anspruch und ist teuer, wenn N sehr groß ist. Ich habe mich gefragt, ob es effiziente Datenstrukturen oder Methoden für eine effiziente Ähnlichkeitssuche gibt. Vielen Dank

Sie können einen Hashing-Vektorisierer für Ihre Dokumente verwenden. Das Ergebnis ist eine Liste von Vektoren. Vektorisieren Sie dann Ihre Ngramme auf die gleiche Weise und berechnen Sie die Projektion dieses neuen Vektors auf die alten. Dies entspricht dem Datenbank-Join für einen Index, hat jedoch möglicherweise weniger Overhead.

Die Datenstruktur, die normalerweise verwendet wird, ist ein invertierter Index (z. B. in Datenbanken).

Bitte beachten Sie, dass das Abgleichen aller Ngram eine gute Heuristik ist, die Sie jedoch möglicherweise verbessern möchten.

Unter Berücksichtigung der Wahrscheinlichkeit jedes Begriffs und des Stemmings können Sie davon profitieren.

Tabelle

ngram
docID

PK (Primärschlüssel) ngram, docID

Abhängig davon kann sich die Datenbank etwas ändern, dies gilt jedoch für TSQL.
x ist das Dokument, mit dem Sie übereinstimmen

select top(1) with ties *    
from 
(  select tm.docID, count(*) as count 
     from table td
     join table tm
       on tm.docID <> td.docID 
      and tm.ngram = td.ngram 
      and td.docID = x
    group by tm.docID 
) tt 
order by count desc

Der Join befindet sich in einem Index (PK), dies ist also sehr schnell. Ich mache das mit einer Million Dokumenten in nur wenigen Sekunden (unter fortgeschritteneren Bedingungen).

Dies wird größere Dokumente begünstigen, aber darum haben Sie gebeten.

Die Frage scheint sich zu ändern

declare table @query (varchar ngram);
insert into @query values ('ng1'), ('ng2'), ('ng3');
select top(10) with ties *    
from 
(  select tm.docID, count(*) as count 
     from table td
     join @query
       on tm.ngram = @query.ngram
    group by tm.docID 
) tt 
order by count desc

Aus Ihrer Klarstellung -

Nehmen wir einfach an, dass es nach Datenbank eine große Liste des ngram-Modells gibt, das das Dokument darstellt

Sie sollten etwas strukturierteres tun und die Daten in eine relationale Datenbank stellen. Auf diese Weise können Sie einfacher und schneller detailliertere Analysen durchführen.

Ich denke, wenn Sie "ngram" sagen, meinen Sie "1gram". Sie können die Analyse auf Wunsch um 2 Gramm, 3 Gramm usw. erweitern.

Ich hätte eine Tabellenstruktur, die ungefähr so ​​aussieht -

1 Gramm
ID-
Wert

Docs
ID
DocTitle
DocAuthor
usw.

Docs1Grams
1GramID
DocID
1GramCount

Wenn also in der Aufzeichnung in der Docs1Grams- Tabelle 1GramID auf 1 Gramm "the" und DocID auf das Dokument "War and Peace" zeigt, enthält 1GramCount die Häufigkeit, mit der 1 Gramm "the" in War and Peace angezeigt wird.

Wenn die DocID für "Krieg und Frieden" 1 und die DocId für "Herr der Ringe" 2 ist, würden Sie diese Abfrage durchführen, um die 1-Gramm-Ähnlichkeitsbewertung für diese beiden Dokumente zu berechnen.

Select count(*) from Docs1Grams D1, Docs1Grams D2   
where D1.DocID = 1 and   
D2.DocID = 2 and   
D1.1GramID = D2.1GramID and   
D1.1GramCount > 0 and   
D2.1GramCount > 0   

Durch Verallgemeinern und Erweitern der Abfrage kann dies leicht geändert werden, um automatisch die höchste Punktzahl / Anzahl auszuwählen und das ausgewählte Dokument mit allen anderen zu vergleichen.

Durch Ändern / Erweitern des D1.1GramCount > 0 and D2.1GramCount > 0Teils der Abfrage können Sie den Vergleich leicht verfeinern, indem Sie beispielsweise 2 Gramm, 3 Gramm usw. hinzufügen oder die einfache Übereinstimmung ändern, um entsprechend der prozentualen Übereinstimmung pro Gramm zu punkten.

Wenn in Ihrem Betreff-Dokument 0,0009% der 1 Gramm "das" sind, Dokument 1 0,001% und Dokument 2 0,0015%, würde Dokument 1 bei "dem" eine höhere Punktzahl erzielen, da der Modul der Differenz (oder ein anderes von Ihnen gewähltes Maß) zu verwenden) ist kleiner.

Wenn Sie überprüfen möchten, ob Ihre n Gramm im Dokument vorhanden sind, müssen Sie das Abfragedokument auch in n Gramm konvertieren. Um dies zu erreichen, können Sie den TFIDF-Vektorisierer verwenden.

from nltk.tokenize import word_tokenize               
from sklearn.feature_extraction.text import TfidfVectorizer
vect = TfidfVectorizer(tokenizer=word_tokenize,ngram_range=(1,2), binary=True, max_features=10000)
TFIDF=vect.fit_transform(df_lvl0['processed_cv_data'])

Um den obigen Code zu erklären:
word_tokenize : Diese Funktion konvertiert den Text in Zeichenfolgentoken, aber Sie müssen die Daten entsprechend bereinigen.
ngram_range : Legt die Anzahl der benötigten ngrams fest. In diesem Fall werden sowohl 1 Wort als auch 2 Wörter benötigt.
max_features : begrenzt die Gesamtzahl. von Funktionen. Ich empfehle es zu verwenden, wenn Sie ein paar Dokumente als Nr. Tokenisieren möchten. der Merkmale ist sehr hoch (in der Größenordnung von 10 ^ 6).

Nachdem Sie das Modell angepasst haben, werden die Funktionen in "vect" gespeichert. Sie können sie anzeigen mit:

keywords=set(vect.get_feature_names())

Nachdem Sie die Gramme Ihres Abfragedokuments in einem Satz gespeichert haben, können Sie Satzoperationen ausführen, die im Vergleich zu Schleifen viel schneller sind. Selbst wenn die Länge jedes Satzes in der Größenordnung von 10 ^ 5 liegt, erhalten Sie Ergebnisse in Sekunden. Ich empfehle dringend, Sets in Python auszuprobieren.

matching_keys = keywords.intersection(all_grams)   //all_grams is the set of your collected grams

Schließlich erhalten Sie alle passenden Schlüsselwörter in "Matching_keys".