Najskuteczniejszy sposób na znalezienie K najczęściej używanych słów w sekwencji wielkich słów

Dane wejściowe: dodatnia liczba całkowita K i duży tekst. Tekst można w rzeczywistości postrzegać jako ciąg słów. Więc nie musimy się martwić, jak podzielić to na ciąg słów.
Wynik: Najczęstsze K słów w tekście.

Moje myślenie jest takie.

1. użyj tablicy Hash, aby zapisać częstotliwość wszystkich słów podczas przechodzenia przez całą sekwencję słów. W tej fazie kluczem jest „słowo”, a wartością jest „częstotliwość słów”. To zajmuje O (n) czasu.

2. sortować parę (słowo, częstotliwość słów); a kluczem jest „częstotliwość słów”. To zajmuje O (n * lg (n)) czasu przy normalnym algorytmie sortowania.

3. Po sortowaniu bierzemy tylko pierwsze K słów. To zajmuje O (K) czasu.

Podsumowując, całkowity czas wynosi O (n + n lg (n) + K) ， Ponieważ K jest na pewno mniejsze od N, więc w rzeczywistości wynosi O (n lg (n)).

Możemy to poprawić. Właściwie chcemy tylko najlepszych słów K. Innymi słowy, częstotliwość nie dotyczy nas. Możemy więc użyć „częściowego sortowania sterty”. W kroku 2) i 3) nie zajmujemy się tylko sortowaniem. Zamiast tego zmieniamy go na

2 ') zbuduj stos par (słowo, częstotliwość słowa) z kluczem „częstotliwość słowa”. Zbudowanie sterty zajmuje O (n) czasu;

3 ') wyodrębnij górne K słów ze stosu. Każda ekstrakcja to O (lg (n)). Zatem całkowity czas wynosi O (k * lg (n)).

Podsumowując, to rozwiązanie kosztuje czas O (n + k * lg (n)).

To tylko moja myśl. Nie znalazłem sposobu na ulepszenie kroku 1).
Mam nadzieję, że niektórzy eksperci ds. Wyszukiwania informacji mogą rzucić więcej światła na to pytanie.

Można to zrobić w czasie O (n)

Rozwiązanie 1:

Kroki:

1. Policz słowa i zhaszuj, co trafi do takiej struktury

   var hash = {
     "I" : 13,
     "like" : 3,
     "meow" : 3,
     "geek" : 3,
     "burger" : 2,
     "cat" : 1,
     "foo" : 100,
     ...
     ...
   

2. Przejdź przez hash i znajdź najczęściej używane słowo (w tym przypadku „foo” 100), a następnie utwórz tablicę o tym rozmiarze

3. Następnie możemy ponownie przejść przez hash i użyć liczby wystąpień słów jako indeksu tablicy, jeśli nie ma nic w indeksie, utworzyć tablicę, w przeciwnym razie dołącz ją do tablicy. Następnie otrzymujemy tablicę taką jak:

     0   1      2            3                  100
   [[ ],[cat],[burger],[like, meow, geek],[]...[foo]]
   

4. Następnie po prostu przejdź przez tablicę od końca i zbierz k słów.

Rozwiązanie 2:

Kroki:

1. Tak samo jak powyżej
2. Użyj sterty min i zachowaj rozmiar sterty min na k, a dla każdego słowa w haszu porównujemy wystąpienia słów z min, 1) jeśli jest większe niż wartość min, usuń min (jeśli rozmiar min sterta równa się k) i wstaw liczbę do sterty min. 2) odpocząć w prostych warunkach.
3. Po przejściu przez tablicę po prostu konwertujemy stertę minimalną na tablicę i zwracamy tablicę.

Nie uzyskasz ogólnie lepszego czasu działania niż rozwiązanie, które opisałeś. Musisz wykonać co najmniej O (n) pracę, aby ocenić wszystkie słowa, a następnie O (k) dodatkową pracę, aby znaleźć k najlepszych terminów.

Jeśli zestaw problemów jest naprawdę duży, możesz użyć rozwiązania rozproszonego, takiego jak mapowanie / redukcja. Niech n robotników mapy policzy częstotliwości na 1 / n-tej części tekstu i dla każdego słowa wyślij je do jednego z m pracowników redukujących obliczonych na podstawie skrótu słowa. Następnie reduktory sumują liczby. Sortuj według wyników reduktorów daje najpopularniejsze słowa w kolejności popularności.

Mała wariacja na temat twojego rozwiązania daje algorytm O (n) , jeśli nie zależy nam na uszeregowaniu najwyższego K, i rozwiązanie O (n + k * lg (k)) , jeśli to zrobimy. Uważam, że obie te granice są optymalne w ramach stałego czynnika.

Optymalizacja pojawia się ponownie po przejrzeniu listy i wstawieniu do tablicy skrótów. Możemy użyć algorytmu mediany median , aby wybrać K-ty największy element na liście. Ten algorytm jest możliwy do udowodnienia O (n).

Po wybraniu najmniejszego elementu Kth dzielimy listę wokół tego elementu, tak jak w quicksort. Jest to oczywiście również O (n). Wszystko po „lewej” stronie osi znajduje się w naszej grupie elementów K, więc gotowe (możemy po prostu wyrzucić wszystko inne w trakcie).

Więc ta strategia jest taka:

1. Przejrzyj każde słowo i wstaw je do tablicy skrótów: O (n)
2. Wybierz K-ty najmniejszy element: O (n)
3. Partycja wokół tego elementu: O (n)

Jeśli chcesz uszeregować K elementów, po prostu posortuj je za pomocą dowolnego wydajnego sortowania porównawczego w czasie O (k * lg (k)), uzyskując całkowity czas wykonania O (n + k * lg (k)).

Ograniczenie czasu O (n) jest optymalne w ramach stałego czynnika, ponieważ musimy zbadać każde słowo przynajmniej raz.

Ograniczenie czasu O (n + k * lg (k)) jest również optymalne, ponieważ nie ma opartego na porównaniu sposobu sortowania k elementów w czasie krótszym niż k * lg (k).

Jeśli Twoja „duża lista słów” jest wystarczająco duża, możesz po prostu pobrać próbkę i uzyskać szacunki. W przeciwnym razie lubię agregację skrótów.

Edycja :

Przez próbkę mam na myśli wybranie podzbioru stron i obliczenie najczęściej występującego słowa na tych stronach. Zakładając, że wybrałeś strony w rozsądny sposób i wybrałeś statystycznie istotną próbkę, twoje szacunki dotyczące najczęściej występujących słów powinny być rozsądne.

Takie podejście jest naprawdę rozsądne tylko wtedy, gdy masz tak dużo danych, że ich przetwarzanie jest po prostu głupie. Jeśli masz tylko kilka megabajtów, powinieneś być w stanie przedrzeć się przez dane i obliczyć dokładną odpowiedź bez wysiłku, zamiast zawracać sobie głowę obliczeniem oszacowania.

Możesz skrócić czas dalej, dzieląc na partycje za pomocą pierwszej litery słów, a następnie dzieląc największy zestaw wielowyrazowy za pomocą następnego znaku, aż uzyskasz k zestawów pojedynczych słów. Użyłbyś pewnego rodzaju drzewa 256-ścieżkowego z listami częściowych / pełnych słów na liście. Musiałbyś być bardzo ostrożny, aby nie powodować wszędzie kopii łańcuchowych.

Ten algorytm to O (m), gdzie m to liczba znaków. Pozwala to uniknąć zależności od k, co jest bardzo miłe dla dużego k [przy okazji, twój opublikowany czas działania jest nieprawidłowy, powinien wynosić O (n * lg (k)) i nie jestem pewien, co to jest m].

Jeśli uruchomisz oba algorytmy obok siebie, uzyskasz coś, co na pewno jest asymptotycznie optymalnym algorytmem O (min (m, n * lg (k))), ale mój powinien być średnio szybszy, ponieważ nie obejmuje haszowanie lub sortowanie.

Masz błąd w opisie: liczenie zajmuje O (n) czasu, ale sortowanie zajmuje O (m * lg (m)), gdzie m to liczba unikalnych słów. Zwykle jest to znacznie mniej niż całkowita liczba słów, więc prawdopodobnie powinno po prostu zoptymalizować sposób budowania skrótu.

Twój problem jest taki sam jak ten - http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

Użyj Trie i min heap, aby skutecznie go rozwiązać.

Jeśli szukasz listy k najczęściej występujących słów w tekście dla dowolnego praktycznego k i dowolnego języka naturalnego, to złożoność algorytmu nie ma znaczenia.

Wystarczy pobrać , powiedzmy, kilka milionów słów ze swojego tekstu, przetworzyć to za pomocą dowolnego algorytmu w ciągu kilku sekund , a najczęstsze zliczenia będą bardzo dokładne.

Na marginesie, złożoność algorytmu pozorowanego (1. policz wszystkie 2. posortuj liczby 3. wybierz najlepszą) to O (n + m * log (m)), gdzie m to liczba różnych słów w twoim tekst. log (m) jest znacznie mniejszy niż (n / m), więc pozostaje O (n).

Praktycznie liczy się długi krok.

1. Wykorzystaj wydajną pamięć struktury danych do przechowywania słów
2. Użyj MaxHeap, aby znaleźć K najczęściej występujących słów.

Oto kod

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;
    }

}   

}

Oto testy jednostkowe

@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));
}

Aby uzyskać więcej informacji, zapoznaj się z tym przypadkiem testowym

1. użyj tablicy Hash, aby zapisać częstotliwość wszystkich słów podczas przechodzenia przez całą sekwencję słów. W tej fazie kluczem jest „słowo”, a wartością jest „częstotliwość słów”. Zajmuje to O (n) czasu, tak samo jak w przypadku każdego wyjaśnionego powyżej

2. Podczas wstawiania samego w hashmap, zachowaj zestaw drzew (specyficzny dla java, są implementacje w każdym języku) o rozmiarze 10 (k = 10), aby zachować 10 najczęściej występujących słów. Do rozmiaru mniej niż 10, dodawaj go dalej. Jeśli rozmiar jest równy 10, jeśli wstawiony element jest większy niż element minimalny, czyli pierwszy element. Jeśli tak, usuń go i włóż nowy element

Aby ograniczyć rozmiar zbioru drzew, zobacz ten link

Załóżmy, że mamy sekwencję słów „reklama” „reklama” „chłopiec” „duży” „zły” „com” „przyjdź” „zimno”. A K = 2. jak wspomniałeś o „partycjonowaniu przy użyciu pierwszej litery słów”, otrzymaliśmy („reklama”, „reklama”) („chłopiec”, „duży”, „zły”) („com” „przyjdź” „zimno”) ” podzielenie największego zestawu wielowyrazowego przy użyciu następnego znaku aż do uzyskania k zestawów pojedynczych słów. " podzieli („chłopak”, „duży”, „zły”) („com” „przyjdzie” „zimno”), pierwsza partycja („reklama”, „reklama”) zostanie pominięta, podczas gdy „reklama” to w rzeczywistości najczęściej używane słowo.

Być może źle zrozumiałem twój punkt widzenia. Czy możesz szczegółowo opisać proces dotyczący partycji?

Uważam, że ten problem można rozwiązać za pomocą algorytmu O (n). Moglibyśmy przeprowadzić sortowanie w locie. Innymi słowy, sortowanie w tym przypadku jest podproblem tradycyjnego problemu sortowania, ponieważ tylko jeden licznik jest zwiększany o jeden za każdym razem, gdy uzyskujemy dostęp do tablicy skrótów. Początkowo lista jest posortowana, ponieważ wszystkie liczniki są zerowe. Ponieważ zwiększamy liczniki w tabeli skrótów, księgujemy kolejną tablicę wartości skrótu uporządkowanych według częstotliwości w następujący sposób. Za każdym razem, gdy zwiększamy licznik, sprawdzamy jego indeks w tablicy rankingowej i sprawdzamy, czy jego liczba przekracza jego poprzednik na liście. Jeśli tak, zamieniamy te dwa elementy. W związku z tym otrzymujemy rozwiązanie, które jest najwyżej O (n), gdzie n jest liczbą słów w tekście oryginalnym.

Ja też z tym walczyłem i zainspirował mnie @aly. Zamiast sortować później, możemy po prostu zachować wstępnie posortowaną listę słów ( List<Set<String>>), a słowo będzie w zestawie na pozycji X, gdzie X jest bieżącą liczbą słów. Ogólnie rzecz biorąc, tak to działa:

1. dla każdego słowa, zapisać go jako część mapą To wystąpienia: Map<String, Integer>.
2. następnie, w oparciu o liczbę, usuń ją z poprzedniego zestawu zliczeń i dodaj do nowego zestawu zliczania.

Wadą tego jest to, że lista może być duża - można ją zoptymalizować za pomocą TreeMap<Integer, Set<String>>- ale to doda trochę narzutu. Ostatecznie możemy użyć mieszanki HashMap lub naszej własnej struktury danych.

Kod

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

}

Po prostu znajduję inne rozwiązanie tego problemu. Ale nie jestem pewien, czy to prawda. Rozwiązanie:

1. Użyj tablicy Hash, aby zapisać częstotliwość wszystkich słów T (n) = O (n)
2. Wybierz pierwsze k elementów tablicy skrótów i odtwórz je w jednym buforze (którego spacja = k). T (n) = O (k)
3. Za każdym razem najpierw musimy znaleźć bieżący element min bufora i po prostu porównać element min bufora z (n - k) elementami tablicy hash jeden po drugim. Jeśli element tablicy skrótów jest większy niż ten element min bufora, porzuć min bieżącego bufora i dodaj element tablicy skrótów. Więc za każdym razem, gdy znajdujemy najmniejszą w buforze potrzeba T (n) = O (k), i przechodzimy przez całą tablicę skrótów potrzebujemy T (n) = O (n - k). Zatem cała złożoność czasowa tego procesu to T (n) = O ((nk) * k).
4. Po przejściu przez całą tablicę skrótów wynik znajduje się w tym buforze.
5. Złożoność całego czasu: T (n) = O (n) + O (k) + O (kn - k ^ 2) = O (kn + n - k ^ 2 + k). Ponieważ k jest naprawdę mniejsze niż n w ogóle. Zatem dla tego rozwiązania złożoność czasowa wynosi T (n) = O (kn) . To jest czas liniowy, kiedy k jest naprawdę małe. Czy to jest poprawne? Naprawdę nie jestem pewien.

Spróbuj pomyśleć o specjalnej strukturze danych, aby podejść do tego rodzaju problemów. W tym przypadku specjalny rodzaj drzewa, taki jak próba przechowywania łańcuchów w określony sposób, jest bardzo wydajny. Lub drugi sposób na zbudowanie własnego rozwiązania, takiego jak liczenie słów. Wydaje mi się, że ten TB danych byłby w języku angielskim, wtedy mamy ogólnie około 600 000 słów, więc będzie można zapisać tylko te słowa i policzyć, które ciągi będą się powtarzać + to rozwiązanie będzie wymagało wyrażenia regularnego, aby wyeliminować niektóre znaki specjalne. Jestem pewien, że pierwsze rozwiązanie będzie szybsze.

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

To ciekawy pomysł do przeszukania i mógłbym znaleźć ten artykuł związany z Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f

Ponadto istnieje implementacja nim tutaj .

Najprostszy kod, aby uzyskać występowanie najczęściej używanego słowa.

 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])
}

W takich sytuacjach zalecam korzystanie z wbudowanych funkcji Java. Ponieważ są już dobrze przetestowane i stabilne. W tym zadaniu powtórzenia słów znajduję za pomocą struktury danych HashMap. Następnie przekazuję wyniki do tablicy obiektów. Sortuję obiekt według Arrays.sort () i wypisuję k górnych słów i ich powtórzeń.

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();
        }
    }

}

Więcej informacji można znaleźć pod adresem https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Mam nadzieję, że to pomoże.

**

C ++ 11 Realizacja powyższej myśli

**

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;

}

};