Der effizienteste Weg, um die häufigsten K-Wörter in einer großen Wortfolge zu finden

85

Eingabe: Eine positive ganze Zahl K und ein großer Text. Der Text kann tatsächlich als Wortfolge angesehen werden. Wir müssen uns also keine Gedanken darüber machen, wie wir es in Wortfolgen aufteilen können.
Ausgabe: Die häufigsten K Wörter im Text.

Mein Denken ist so.

  1. Verwenden Sie eine Hash-Tabelle, um die Häufigkeit aller Wörter aufzuzeichnen, während Sie die gesamte Wortfolge durchlaufen. In dieser Phase ist der Schlüssel "Wort" und der Wert ist "Wortfrequenz". Dies dauert O (n) Zeit.

  2. sortiere das (Wort, Wort-Frequenz) Paar; und der Schlüssel ist "Worthäufigkeit". Dies dauert bei normalem Sortieralgorithmus O (n * lg (n)).

  3. Nach dem Sortieren nehmen wir nur die ersten K Wörter. Dies dauert O (K) Zeit.

Zusammenfassend ist die Gesamtzeit O (n + n lg (n) + K) , Da K sicherlich kleiner als N ist, ist es tatsächlich O (n lg (n)).

Wir können das verbessern. Eigentlich wollen wir nur Top-K-Wörter. Mit anderen Worten, die Häufigkeit ist für uns nicht von Belang. Wir können also "partielle Heap-Sortierung" verwenden. In Schritt 2) und 3) sortieren wir nicht nur. Stattdessen ändern wir es so

2 ') einen Haufen von (Wort-, Wortfrequenz-) Paaren mit "Wortfrequenz" als Schlüssel aufbauen. Es dauert O (n) Zeit, um einen Heap zu erstellen;

3 ') extrahiere die obersten K Wörter aus dem Haufen. Jede Extraktion ist O (lg (n)). Die Gesamtzeit beträgt also O (k * lg (n)).

Zusammenfassend kostet diese Lösung Zeit O (n + k * lg (n)).

Das ist nur mein Gedanke. Ich habe keinen Weg gefunden, um Schritt 1) ​​zu verbessern.
Ich hoffe, dass einige Experten für Information Retrieval mehr Licht in diese Frage bringen können.

Morgan Cheng
quelle
Würden Sie für die O-Sortierung (n * logn) Merge-Sortierung oder Quicksortierung verwenden?
committedandroider
1
Für den praktischen Gebrauch ist Aaron Maenpaas Antwort , auf eine Probe zu zählen, am besten. Es ist nicht so, dass sich die häufigsten Wörter aus Ihrer Stichprobe verstecken. Für Sie Komplexitätsfreaks ist es O (1), da die Größe der Stichprobe festgelegt ist. Sie erhalten nicht die genauen Zählungen, aber Sie fragen auch nicht nach ihnen.
Nikana Reklawyks
Wenn Sie eine Überprüfung Ihrer Komplexitätsanalyse wünschen, sollte ich besser erwähnen: Wenn n die Anzahl der Wörter in Ihrem Text und m die Anzahl der verschiedenen Wörter (Typen, die wir sie nennen) ist, ist Schritt 1 O ( n ), aber Schritt 2 ist O ( m .lg ( m )) und m << n (Sie haben möglicherweise Milliarden Wörter und erreichen nicht eine Million Typen, probieren Sie es aus). Selbst mit einem Dummy-Algorithmus ist es also immer noch O ( n + m lg ( m )) = O ( n ).
Nikana Reklawyks
1
Bitte fügen Sie der Frage eine Annahme hinzu, dass wir genug Hauptspeicher haben, um alle Wörter des großen Textes aufzunehmen. Es wäre interessant, Ansätze zu sehen, um k = 100 Wörter aus einer 10-GB-Datei zu finden (dh alle Wörter passen nicht in 4 GB RAM) !!
KGhatak
@KGhatak wie würden wir es machen, wenn es die RAM-Größe überschreitet?
user7098526

Antworten:

65

Dies kann in O (n) Zeit erfolgen

Lösung 1:

Schritte:

  1. Zähle die Wörter und hashe sie, was in der Struktur wie dieser endet

    var hash = {
      "I" : 13,
      "like" : 3,
      "meow" : 3,
      "geek" : 3,
      "burger" : 2,
      "cat" : 1,
      "foo" : 100,
      ...
      ...
    
  2. Durchlaufen Sie den Hash und suchen Sie das am häufigsten verwendete Wort (in diesem Fall "foo" 100). Erstellen Sie dann das Array dieser Größe

  3. Dann können wir den Hash erneut durchlaufen und die Anzahl der vorkommenden Wörter als Array-Index verwenden. Wenn der Index nichts enthält, erstellen Sie ein Array, und fügen Sie es dem Array hinzu. Dann erhalten wir ein Array wie:

      0   1      2            3                  100
    [[ ],[cat],[burger],[like, meow, geek],[]...[foo]]
    
  4. Dann durchlaufen Sie einfach das Array vom Ende und sammeln die k Wörter.

Lösung 2:

Schritte:

  1. Das gleiche wie oben
  2. Verwenden Sie min heap und halten Sie die Größe von min heap auf k. Für jedes Wort im Hash vergleichen wir das Vorkommen von Wörtern mit min. 1) Wenn es größer als der min-Wert ist, entfernen Sie min (wenn die Größe von min heap ist gleich k) und füge die Zahl in den min heap ein. 2) Ruhe einfache Bedingungen.
  3. Nach dem Durchlaufen des Arrays konvertieren wir einfach den min-Heap in ein Array und geben das Array zurück.
Chihung Yu
quelle
16
Ihre Lösung (1) ist eine O (n) Bucket-Sortierung, die eine Standard-O (n lg n) -Vergleichssortierung ersetzt. Ihr Ansatz erfordert zusätzlichen Platz für die Bucket-Struktur, aber Vergleichssortierungen können an Ort und Stelle durchgeführt werden. Ihre Lösung (2) läuft in der Zeit O (n lg k) - das heißt, O (n), um alle Wörter zu durchlaufen, und O (lg k), um jedes einzelne in den Heap einzufügen.
stackoverflowuser2010
4
Die erste Lösung benötigt zwar mehr Platz, es ist jedoch wichtig zu betonen, dass es sich tatsächlich um O (n) in der Zeit handelt. 1: Hash-Frequenzen, die durch das Wort O (n) eingegeben werden; 2: Frequenz-Hash durchlaufen, zweiten nach Frequenz getasteten Hash erstellen. Dies ist O (n), um den Hash zu durchlaufen, und O (1), um der Liste der Wörter mit dieser Frequenz ein Wort hinzuzufügen. 3: Durchqueren Sie den Hash von der maximalen Frequenz nach unten, bis Sie k treffen. Höchstens O (n). Gesamt = 3 * O (n) = O (n).
BringMyCakeBack
3
In der Regel wird beim Zählen von Wörtern die Anzahl der Buckets in Lösung 1 stark überschätzt (da das häufigste Wort Nummer eins so viel häufiger ist als das zweit- und drittbeste), sodass Ihr Array spärlich und ineffizient ist.
Nikana Reklawyks
Ihre Lösung Nr. 1 funktioniert nicht, wenn k (die Anzahl der häufigen Wörter) kleiner ist als die Anzahl der Vorkommen des häufigsten Wortes (dh 100 in diesem Fall). Natürlich kann dies in der Praxis nicht vorkommen, aber man sollte es tun nicht annehmen!
Eins Zwei Drei
@OneTwoThree Die vorgeschlagene Lösung ist nur ein Beispiel. Die Nummer richtet sich nach der Nachfrage.
Chihung Yu
22

Sie erhalten im Allgemeinen keine bessere Laufzeit als die von Ihnen beschriebene Lösung. Sie müssen mindestens O (n) arbeiten, um alle Wörter zu bewerten, und dann O (k) zusätzliche Arbeit, um die Top-k-Begriffe zu finden.

Wenn Ihr Problem sehr groß ist, können Sie eine verteilte Lösung wie Map / Reduce verwenden. Lassen Sie n Kartenarbeiter die Häufigkeit auf jeweils 1 / n des Textes zählen und senden Sie sie für jedes Wort an einen der m Reduzierer, die anhand des Hash des Wortes berechnet wurden. Die Reduzierer summieren dann die Zählungen. Wenn Sie die Sortierung über die Ausgänge der Reduzierungen zusammenführen, erhalten Sie die beliebtesten Wörter in der Reihenfolge ihrer Beliebtheit.

Nick Johnson
quelle
13

Eine kleine Variation Ihrer Lösung ergibt einen O (n) -Algorithmus, wenn es uns nicht darum geht, die oberste K zu klassifizieren, und eine O (n + k * lg (k)) - Lösung, wenn wir dies tun. Ich glaube, diese beiden Grenzen sind innerhalb eines konstanten Faktors optimal.

Die Optimierung erfolgt hier erneut, nachdem wir die Liste durchlaufen und in die Hash-Tabelle eingefügt haben. Wir können den Median des Median- Algorithmus verwenden, um das k-te größte Element in der Liste auszuwählen. Dieser Algorithmus ist nachweislich O (n).

Nachdem wir das kleinste K-te Element ausgewählt haben, teilen wir die Liste genau wie bei Quicksort um dieses Element auf. Dies ist offensichtlich auch O (n). Alles auf der "linken" Seite des Pivots befindet sich in unserer Gruppe von K Elementen, also sind wir fertig (wir können einfach alles andere wegwerfen, während wir weitergehen).

Diese Strategie lautet also:

  1. Gehen Sie jedes Wort durch und fügen Sie es in eine Hash-Tabelle ein: O (n)
  2. Wählen Sie das K-te kleinste Element aus: O (n)
  3. Partition um dieses Element: O (n)

Wenn Sie die K-Elemente einordnen möchten, sortieren Sie sie einfach mit einer effizienten Vergleichssortierung in O (k * lg (k)), was eine Gesamtlaufzeit von O (n + k * lg (k)) ergibt.

Die O (n) -Zeitgrenze ist innerhalb eines konstanten Faktors optimal, da wir jedes Wort mindestens einmal untersuchen müssen.

Die zeitgebundene O (n + k * lg (k)) - Zeit ist ebenfalls optimal, da es keine vergleichsbasierte Möglichkeit gibt, k Elemente in weniger als k * lg (k) Zeit zu sortieren.


quelle
Wenn wir das kleinste K-te Element auswählen, wird der kleinste K-te Hash-Schlüssel ausgewählt. Es ist nicht notwendig, dass die linke Partition von Schritt 3 genau K Wörter enthält.
Prakash Murali
2
Sie können keine "Mediane der Mediane" auf dem Hash-Tisch ausführen, da dies beim Tauschen der Fall ist. Sie müssten die Daten aus der Hash-Tabelle in ein temporäres Array kopieren. Daher ist O (n) -Speicher erforderlich.
user674669
Ich verstehe nicht, wie Sie das K-te kleinste Element in O (n) auswählen können.
Michael Ho Chum
Überprüfen Sie dies für den Algorithmus zum Finden des K-ten kleinsten Elements in O (n) - wikiwand.com/de/Median_of_medians
Piyush
Die Komplexität ist auch dann gleich, wenn Sie Hash-Tabelle + Min-Heap verwenden. Ich sehe keine Optimierung.
Vinay
8

Wenn Ihre "große Wortliste" groß genug ist, können Sie einfach eine Stichprobe erstellen und Schätzungen abrufen. Ansonsten mag ich Hash-Aggregation.

Bearbeiten :

Mit Beispiel meine ich, wählen Sie eine Teilmenge von Seiten und berechnen Sie das häufigste Wort auf diesen Seiten. Vorausgesetzt, Sie wählen die Seiten in angemessener Weise aus und wählen eine statistisch signifikante Stichprobe aus, sollten Ihre Schätzungen der häufigsten Wörter angemessen sein.

Dieser Ansatz ist wirklich nur dann sinnvoll, wenn Sie so viele Daten haben, dass die Verarbeitung einfach nur albern ist. Wenn Sie nur ein paar Megabyte haben, sollten Sie in der Lage sein, die Daten zu durchbrechen und eine genaue Antwort zu berechnen, ohne ins Schwitzen zu geraten, anstatt sich die Mühe zu machen, eine Schätzung zu berechnen.

Aaron Maenpaa
quelle
Manchmal müssen Sie dies mehrmals tun, beispielsweise wenn Sie versuchen, die Liste der häufigsten Wörter pro Website oder Thema abzurufen. In diesem Fall schneidet "ohne ins Schwitzen zu geraten" nicht wirklich. Sie müssen noch einen Weg finden, dies so effizient wie möglich zu tun.
itsadok
1
+1 für eine praktische Antwort, die die irrelevanten Komplexitätsprobleme nicht anspricht. @itsadok: Für jeden Lauf: Wenn es groß genug ist, probieren Sie es aus; Wenn dies nicht der Fall ist, ist es irrelevant, einen Log-Faktor zu erhalten.
Nikana Reklawyks
2

Sie können die Zeit weiter verkürzen, indem Sie mit dem ersten Buchstaben von Wörtern partitionieren und dann den größten Mehrwortsatz mit dem nächsten Zeichen partitionieren, bis Sie k Einzelwortsätze haben. Sie würden eine Art 256-Wege-Baum mit Listen von Teil- / vollständigen Wörtern an den Blättern verwenden. Sie müssen sehr vorsichtig sein, um nicht überall String-Kopien zu verursachen.

Dieser Algorithmus ist O (m), wobei m die Anzahl der Zeichen ist. Es vermeidet diese Abhängigkeit von k, was für große k sehr schön ist [da Ihre angegebene Laufzeit falsch ist, sollte es O (n * lg (k)) sein, und ich bin mir nicht sicher, was das bedeutet m].

Wenn Sie beide Algorithmen nebeneinander ausführen, erhalten Sie einen asymptotisch optimalen O-Algorithmus (min (m, n * lg (k))), der meiner Meinung nach im Durchschnitt schneller sein sollte, da er nicht involviert ist Hashing oder Sortieren.


quelle
7
Was Sie beschreiben, wird als "Trie" bezeichnet.
Nick Johnson
Hallo Strilanc. Können Sie den Prozess der Partitionierung im Detail erklären?
Morgan Cheng
1
Wie geht es dabei nicht um Sortieren? Wenn Sie den Versuch gemacht haben, wie können Sie die k Wörter mit den größten Frequenzen herausreißen? macht keinen Sinn
gewöhnlicher
2

Ihre Beschreibung enthält einen Fehler: Das Zählen dauert O (n), das Sortieren jedoch O (m * lg (m)), wobei m die Anzahl der eindeutigen Wörter ist. Dies ist normalerweise viel kleiner als die Gesamtzahl der Wörter, daher sollte wahrscheinlich nur optimiert werden, wie der Hash erstellt wird.

Martinus
quelle
2

Wenn Sie nach der Liste der k häufigsten Wörter in Ihrem Text für ein praktisches k und für eine natürliche Sprache suchen, ist die Komplexität Ihres Algorithmus nicht relevant.

Nur Probe , sagen wir, ein paar Millionen Wörter aus dem Text, Verfahren , dass mit jedem Algorithmus in einer Angelegenheit von Sekunden , und die häufigsten Zählungen sehr genau sein.

Als Randnotiz ist die Komplexität des Dummy-Algorithmus (1. alle zählen 2. die Zählungen sortieren 3. die besten nehmen) O (n + m * log (m)), wobei m die Anzahl der verschiedenen Wörter in Ihrem ist Text. log (m) ist viel kleiner als (n / m), also bleibt es O (n).

Praktisch zählt der lange Schritt.

Nikana Reklawyks
quelle
2
  1. Verwenden Sie eine speichereffiziente Datenstruktur, um die Wörter zu speichern
  2. Verwenden Sie MaxHeap, um die häufigsten K-Wörter zu finden.

Hier ist der Code

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import com.nadeem.app.dsa.adt.Trie;
import com.nadeem.app.dsa.adt.Trie.TrieEntry;
import com.nadeem.app.dsa.adt.impl.TrieImpl;

public class TopKFrequentItems {

private int maxSize;

private Trie trie = new TrieImpl();
private PriorityQueue<TrieEntry> maxHeap;

public TopKFrequentItems(int k) {
    this.maxSize = k;
    this.maxHeap = new PriorityQueue<TrieEntry>(k, maxHeapComparator());
}

private Comparator<TrieEntry> maxHeapComparator() {
    return new Comparator<TrieEntry>() {
        @Override
        public int compare(TrieEntry o1, TrieEntry o2) {
            return o1.frequency - o2.frequency;
        }           
    };
}

public void add(String word) {
    this.trie.insert(word);
}

public List<TopK> getItems() {

    for (TrieEntry trieEntry : this.trie.getAll()) {
        if (this.maxHeap.size() < this.maxSize) {
            this.maxHeap.add(trieEntry);
        } else if (this.maxHeap.peek().frequency < trieEntry.frequency) {
            this.maxHeap.remove();
            this.maxHeap.add(trieEntry);
        }
    }
    List<TopK> result = new ArrayList<TopK>();
    for (TrieEntry entry : this.maxHeap) {
        result.add(new TopK(entry));
    }       
    return result;
}

public static class TopK {
    public String item;
    public int frequency;

    public TopK(String item, int frequency) {
        this.item = item;
        this.frequency = frequency;
    }
    public TopK(TrieEntry entry) {
        this(entry.word, entry.frequency);
    }
    @Override
    public String toString() {
        return String.format("TopK [item=%s, frequency=%s]", item, frequency);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + frequency;
        result = prime * result + ((item == null) ? 0 : item.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        TopK other = (TopK) obj;
        if (frequency != other.frequency)
            return false;
        if (item == null) {
            if (other.item != null)
                return false;
        } else if (!item.equals(other.item))
            return false;
        return true;
    }

}   

}}

Hier sind die Unit-Tests

@Test
public void test() {
    TopKFrequentItems stream = new TopKFrequentItems(2);

    stream.add("hell");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hero");
    stream.add("hero");
    stream.add("hero");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("home");
    stream.add("go");
    stream.add("go");
    assertThat(stream.getItems()).hasSize(2).contains(new TopK("hero", 3), new TopK("hello", 8));
}

Weitere Einzelheiten finden Sie in diesem Testfall

craftsmannadeem
quelle
1
  1. Verwenden Sie eine Hash-Tabelle, um die Häufigkeit aller Wörter aufzuzeichnen, während Sie die gesamte Wortfolge durchlaufen. In dieser Phase ist der Schlüssel "Wort" und der Wert ist "Wortfrequenz". Dies dauert O (n) Zeit. Dies ist das gleiche wie bei jedem oben erläuterten

  2. Behalten Sie beim Einfügen in die Hashmap das Treeset (spezifisch für Java, es gibt Implementierungen in jeder Sprache) der Größe 10 (k = 10) bei, um die 10 häufigsten Wörter beizubehalten. Bis die Größe weniger als 10 beträgt, fügen Sie sie hinzu. Wenn die Größe gleich 10 ist, wenn das eingefügte Element größer als das minimale Element ist, dh das erste Element. Wenn ja, entfernen Sie es und fügen Sie ein neues Element ein

Informationen zum Einschränken der Größe des Baumsatzes finden Sie unter diesem Link

M Sach
quelle
0

Angenommen, wir haben eine Wortfolge "ad" "ad" "boy" "big" "bad" "com" "come" "cold". Und K = 2. Wie Sie erwähnt haben "Partitionierung mit dem ersten Buchstaben", haben wir dann ("Anzeige", "Anzeige") ("Junge", "groß", "schlecht") ("com" "kommen" "kalt") " Partitionieren des größten Mehrwortsatzes mit dem nächsten Zeichen, bis Sie k Einzelwortsätze haben. " es wird partitioniert ("Junge", "groß", "schlecht") ("com" "kommt" "kalt"), die erste Partition ("Anzeige", "Anzeige") wird übersehen, während "Anzeige" tatsächlich die ist häufigstes Wort.

Vielleicht verstehe ich Ihren Standpunkt falsch. Können Sie bitte Ihren Prozess bezüglich der Partition detaillieren?

Morgan Cheng
quelle
0

Ich glaube, dieses Problem kann durch einen O (n) -Algorithmus gelöst werden. Wir könnten die Sortierung im laufenden Betrieb durchführen. Mit anderen Worten, die Sortierung ist in diesem Fall ein Unterproblem des herkömmlichen Sortierproblems, da bei jedem Zugriff auf die Hash-Tabelle nur ein Zähler um eins erhöht wird. Zu Beginn wird die Liste sortiert, da alle Zähler Null sind. Während wir die Zähler in der Hash-Tabelle weiter inkrementieren, führen wir ein weiteres Array von Hash-Werten, die nach Häufigkeit geordnet sind, wie folgt. Jedes Mal, wenn wir einen Zähler erhöhen, überprüfen wir seinen Index im Rangarray und prüfen, ob seine Anzahl den Vorgänger in der Liste überschreitet. Wenn ja, tauschen wir diese beiden Elemente aus. Als solche erhalten wir eine Lösung, die höchstens O (n) ist, wobei n die Anzahl der Wörter im Originaltext ist.

Aly Farahat
quelle
Dies ist im Allgemeinen eine gute Richtung - aber es hat einen Fehler. Wenn die Anzahl erhöht wird, überprüfen wir nicht nur "seinen Vorgänger", sondern müssen auch die "Vorgänger" überprüfen. Zum Beispiel besteht eine große Chance, dass das Array [4,3,1,1,1,1,1,1,1,1,1] ist - die Einsen können so viele sein -, dass es weniger effizient ist da müssen wir alle Vorgänger durchsehen, um den richtigen zum Tauschen zu finden.
Shawn
Wäre das nicht viel schlimmer als O (n)? Eher wie O (n ^ 2), da es im Wesentlichen eine ziemlich ineffiziente Sorte ist?
dcarr622
Hallo Shawn. Ja, ich stimme dir zu. Ich vermute jedoch, dass das von Ihnen erwähnte Problem für das Problem von grundlegender Bedeutung ist. Wenn wir nicht nur ein sortiertes Array von Werten beibehalten, sondern auch ein Array von (Wert-, Index-) Paaren beibehalten könnten, wobei der Index auf das erste Auftreten des wiederholten Elements verweist, sollte das Problem in O lösbar sein (n) Zeit. Zum Beispiel sieht [4,3,1,1,1,1,1,1,1,1,1] wie [(4,0), (3,1), (1,2), (1) aus , 2), (1,2, ..., (1,2)]; die Indizes beginnen bei 0.
Aly Farahat
0

Ich hatte auch damit zu kämpfen und ließ mich von @aly inspirieren. Anstatt danach zu sortieren, können wir einfach eine vorsortierte Liste von Wörtern ( List<Set<String>>) pflegen, und das Wort befindet sich in der Menge an Position X, wobei X die aktuelle Anzahl des Wortes ist. Im Allgemeinen funktioniert es folgendermaßen:

  1. Speichern Sie es für jedes Wort als Teil der Karte seines Auftretens: Map<String, Integer> .
  2. Entfernen Sie es dann basierend auf der Anzahl aus dem vorherigen Zählsatz und fügen Sie es dem neuen Zählsatz hinzu.

Der Nachteil dabei ist, dass die Liste möglicherweise groß ist - kann mithilfe von a optimiert werden TreeMap<Integer, Set<String>> -, aber dies erhöht den Overhead. Letztendlich können wir eine Mischung aus HashMap oder unserer eigenen Datenstruktur verwenden.

Der Code

public class WordFrequencyCounter {
    private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars
    Map<String, MutableCounter> counters = new HashMap<String, MutableCounter>();
    List<Set<String>> reverseCounters = new ArrayList<Set<String>>();

    private static class MutableCounter {
        int i = 1;
    }

    public List<String> countMostFrequentWords(String text, int max) {
        int lastPosition = 0;
        int length = text.length();
        for (int i = 0; i < length; i++) {
            char c = text.charAt(i);
            if (c <= WORD_SEPARATOR_MAX) {
                if (i != lastPosition) {
                    String word = text.substring(lastPosition, i);
                    MutableCounter counter = counters.get(word);
                    if (counter == null) {
                        counter = new MutableCounter();
                        counters.put(word, counter);
                    } else {
                        Set<String> strings = reverseCounters.get(counter.i);
                        strings.remove(word);
                        counter.i ++;
                    }
                    addToReverseLookup(counter.i, word);
                }
                lastPosition = i + 1;
            }
        }

        List<String> ret = new ArrayList<String>();
        int count = 0;
        for (int i = reverseCounters.size() - 1; i >= 0; i--) {
            Set<String> strings = reverseCounters.get(i);
            for (String s : strings) {
                ret.add(s);
                System.out.print(s + ":" + i);
                count++;
                if (count == max) break;
            }
            if (count == max) break;
        }
        return ret;
    }

    private void addToReverseLookup(int count, String word) {
        while (count >= reverseCounters.size()) {
            reverseCounters.add(new HashSet<String>());
        }
        Set<String> strings = reverseCounters.get(count);
        strings.add(word);
    }

}
Shawn
quelle
0

Ich finde gerade die andere Lösung für dieses Problem heraus. Aber ich bin nicht sicher, ob es richtig ist. Lösung:

  1. Verwenden Sie eine Hash-Tabelle, um die Häufigkeit aller Wörter T (n) = O (n) aufzuzeichnen.
  2. Wählen Sie die ersten k Elemente der Hash-Tabelle aus und stellen Sie sie in einem Puffer wieder her (dessen Leerzeichen = k). T (n) = O (k)
  3. Jedes Mal müssen wir zuerst das aktuelle min-Element des Puffers finden und das min-Element des Puffers nacheinander mit den (n - k) -Elementen der Hash-Tabelle vergleichen. Wenn das Element der Hash-Tabelle größer als dieses min-Element des Puffers ist, löschen Sie das min des aktuellen Puffers und fügen Sie das Element der Hash-Tabelle hinzu. Jedes Mal, wenn wir die minimale im Puffer finden, brauchen wir T (n) = O (k) und durchlaufen die gesamte Hash-Tabelle, brauchen wir T (n) = O (n - k). Die gesamte Zeitkomplexität für diesen Prozess ist also T (n) = O ((nk) * k).
  4. Nach dem Durchlaufen der gesamten Hash-Tabelle befindet sich das Ergebnis in diesem Puffer.
  5. Die gesamte Zeitkomplexität: T (n) = O (n) + O (k) + O (kn - k ^ 2) = O (kn + n - k ^ 2 + k). Da k im Allgemeinen wirklich kleiner als n ist. Für diese Lösung ist die zeitliche Komplexität also T (n) = O (kn) . Das ist eine lineare Zeit, wenn k wirklich klein ist. Ist es richtig? Ich bin mir wirklich nicht sicher.
zproject89
quelle
0

Versuchen Sie, sich eine spezielle Datenstruktur auszudenken, um diese Art von Problemen anzugehen. In diesem Fall ist eine spezielle Baumart wie der Versuch, Zeichenfolgen auf bestimmte Weise zu speichern, sehr effizient. Oder eine zweite Möglichkeit, eine eigene Lösung wie das Zählen von Wörtern zu erstellen. Ich denke, diese TB Daten wären auf Englisch, dann haben wir im Allgemeinen ungefähr 600.000 Wörter, so dass es möglich sein wird, nur diese Wörter zu speichern und zu zählen, welche Zeichenfolgen wiederholt werden würden + diese Lösung benötigt Regex, um einige Sonderzeichen zu eliminieren. Die erste Lösung wird schneller sein, da bin ich mir ziemlich sicher.

http://en.wikipedia.org/wiki/Trie

blueberry0xff
quelle
0

Einfachster Code, um das Auftreten des am häufigsten verwendeten Wortes zu ermitteln.

 function strOccurence(str){
    var arr = str.split(" ");
    var length = arr.length,temp = {},max; 
    while(length--){
    if(temp[arr[length]] == undefined && arr[length].trim().length > 0)
    {
        temp[arr[length]] = 1;
    }
    else if(arr[length].trim().length > 0)
    {
        temp[arr[length]] = temp[arr[length]] + 1;

    }
}
    console.log(temp);
    var max = [];
    for(i in temp)
    {
        max[temp[i]] = i;
    }
    console.log(max[max.length])
   //if you want second highest
   console.log(max[max.length - 2])
}
ngLover
quelle
0

In diesen Situationen empfehle ich die Verwendung der in Java integrierten Funktionen. Da sind sie schon gut getestet und stabil. In diesem Problem finde ich die Wiederholungen der Wörter mithilfe der HashMap-Datenstruktur. Dann schiebe ich die Ergebnisse auf ein Array von Objekten. Ich sortiere das Objekt nach Arrays.sort () und drucke die obersten k Wörter und ihre Wiederholungen.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class TopKWordsTextFile {

    static class SortObject implements Comparable<SortObject>{

        private String key;
        private int value;

        public SortObject(String key, int value) {
            super();
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(SortObject o) {
            //descending order
            return o.value - this.value;
        }
    }


    public static void main(String[] args) {
        HashMap<String,Integer> hm = new HashMap<>();
        int k = 1;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("words.in")));

            String line;
            while ((line = br.readLine()) != null) {
                // process the line.
                //System.out.println(line);
                String[] tokens = line.split(" ");
                for(int i=0; i<tokens.length; i++){
                    if(hm.containsKey(tokens[i])){
                        //If the key already exists
                        Integer prev = hm.get(tokens[i]);
                        hm.put(tokens[i],prev+1);
                    }else{
                        //If the key doesn't exist
                        hm.put(tokens[i],1);
                    }
                }
            }
            //Close the input
            br.close();
            //Print all words with their repetitions. You can use 3 for printing top 3 words.
            k = hm.size();
            // Get a set of the entries
            Set set = hm.entrySet();
            // Get an iterator
            Iterator i = set.iterator();
            int index = 0;
            // Display elements
            SortObject[] objects = new SortObject[hm.size()];
            while(i.hasNext()) {
                Map.Entry e = (Map.Entry)i.next();
                //System.out.print("Key: "+e.getKey() + ": ");
                //System.out.println(" Value: "+e.getValue());
                String tempS = (String) e.getKey();
                int tempI = (int) e.getValue();
                objects[index] = new SortObject(tempS,tempI);
                index++;
            }
            System.out.println();
            //Sort the array
            Arrays.sort(objects);
            //Print top k
            for(int j=0; j<k; j++){
                System.out.println(objects[j].key+":"+objects[j].value);
            }


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

Weitere Informationen finden Sie unter https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Ich hoffe, es hilft.

Mohammad
quelle
Inwiefern verbessert dies den in der Frage skizzierten Ansatz? (Bitte lassen Sie keine Kommentare aus dem auf SE präsentierten Code aus.) ( I recommend to use Java built-in featuresWie foreach Schleifen und Streams Verarbeitung ?)
Greybeard
Wie Sie wissen, ist die Auswahl der richtigen Datenstruktur einer der wichtigsten Faktoren beim Entwurf eines effizienten Algorithmus. Dann ist es wichtig, wie Sie sich dem Problem nähern. Zum Beispiel müssen Sie ein Problem durch Teilen und Erobern angreifen. Sie müssen einen anderen durch Gier angreifen. Wie Sie wissen, arbeitet das Unternehmen Oracle an Java. Sie sind eines der besten Technologieunternehmen der Welt. Es gibt einige der brillantesten Ingenieure, die dort an integrierten Java-Funktionen arbeiten. Diese Funktionen sind also gut getestet und kugelsicher. Wenn wir sie nutzen können, ist es meiner Meinung nach besser, sie zu nutzen.
Mohammad
0
**

C ++ 11 Implementierung des obigen Gedankens

** **.

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {

    unordered_map<int,int> map;
    for(int num : nums){
        map[num]++;
    }

    vector<int> res;
    // we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue
    // pair<first, second>: first is frequency,  second is number 
    priority_queue<pair<int,int>> pq; 
    for(auto it = map.begin(); it != map.end(); it++){
        pq.push(make_pair(it->second, it->first));

        // onece the size bigger than size-k, we will pop the value, which is the top k frequent element value 

        if(pq.size() > (int)map.size() - k){
            res.push_back(pq.top().second);
            pq.pop();
        }
    }
    return res;

}

};

asad_nitp
quelle