Algorithmus, um eine Eingabedatei mit einer gegebenen Anzahl von Dateien zu vergleichen

Question

Ich hatte letzte Woche ein Interview. Ich war in einer der Fragen in Algorithmus Runde stecken. Ich habe diese Frage beantwortet, aber der Interviewer schien nicht überzeugt zu sein. Deshalb teile ich das Gleiche.

Bitte sagen Sie mir eine optimierte Methode für diese Frage, so dass es mir in zukünftigen Interviews helfen wird.

Frage: -

Es gibt 20 Textdateien angegeben, werden alle Dateien sind ASCII-Textdateien, mit Größe von weniger als 10^9 Byte. Es gibt auch eine Eingabe, das ist auch eine ASCII-Datei, sagen wir, input.txt.

Unsere Aufgabe ist es, den Inhalt dieser Eingabedatei strategisch mit gegebenen 20 Dateien zu vergleichen und den Namen der am nächsten passenden Datei auszudrucken. Der Inhalt der Eingabedatei stimmt möglicherweise nur teilweise überein

Vielen Dank im Voraus. Auf der Suche nach Ihrer freundlichen Antwort.

Answer 1

diff ihnen und durch wc -l oder implementieren Levenshtein distance in C++, jede Zeile als einzelne Zeichen Behandlung (oder jede weitere geeignete Einheit condidering den Gegenstand Domäne)

Answer 2

Sie irgendeine Art von Indexierungs erstellen kann (Beispiel: trie), um die Eingabedatei zusammenzufassen. Dann können Sie prüfen, wie viele Indizes in Dokumenten übereinstimmen.

Eg. Erstellen Sie einen Trie für die Eingabedatei für die Länge 10. Überprüfen Sie für jede Zeichenfolge der Länge 10 (überlappend) in den Textdateien, wie viele davon im Trie übereinstimmen.

Answer 3

Als Vorschlag für die Entwicklung wirklich fähiger, skalierbarer Systeme für Dokumentähnlichkeit empfehle ich Kapitel 3 von Mining Massive Datasets, das online frei verfügbar ist. Ein Ansatz, der hier vorgestellt wird, besteht darin, Datensätze zu "schleppen", indem Wortzählungen in Mengen vektorisiert werden, diese Wortanzahl dann hashend und Familien von Hashwerten mit der Jaccard-Ähnlichkeit verglichen werden, um eine Punktzahl zwischen allen Dokumenten zu erhalten. Dies kann mit Petabytes von Dateien mit hoher Genauigkeit funktionieren, wenn dies richtig gemacht wird. Explizite Details mit guten Diagrammen können aus Stanfords CS246 Slides on Locality Sensitive Hashing abgelesen werden. Einfachere Ansätze wie die Worthäufigkeitszählung werden ebenfalls im Buch beschrieben.