Как найти самое часто встречающееся слово в словесном потоке?

Возможный дубликат:
Поиск максимального повторяющийся элемент в массиве

Если есть поток слов с частотой встречаемости одного слова 51% или более, как мы можем найти наиболее часто встречающееся слово, если это всего лишь строка, и целое число может быть сохранено в памяти за раз, чтобы помочь нам найти его.

Мы можем получить доступ к каждому слову только один раз, так как это поток.

Никакой конкретный язык не требуется, но это в основном предназначено для Java.

Также я не прошу код, просто идею. :)


java restrictions
person GG GG    schedule 18.07.2012    source источник
comment
есть ли ограничение на количество строк или целых чисел, которые вы можете хранить? или ограничение структур данных?   -  person John Kane    schedule 18.07.2012
comment
Вы знаете длину потока?   -  person Garrett Hall    schedule 18.07.2012
comment
Как сказал @assylias, алгоритм голосования Бойера-Мура, безусловно, правильный путь!   -  person Anirudh Ramanathan    schedule 18.07.2012
comment
Я понимаю! В настоящее время я смотрю на него, чтобы увидеть, работает ли он o:   -  person GG GG    schedule 18.07.2012

Ответы (1)


arrow_upward
0
arrow_downward

Для полноты реализации в Java алгоритма, представленного в дубликате, на который я указал, примененный к примеру:

public static void main(String[] args) throws InterruptedException {
    List<String> list = Arrays.asList("a", "b", "c", "a", "d", "e", "a", "a", "b", "b", "a");
    int counter = 0;
    String mostFrequentWord = "";
    for (String streamed : list) {
        if (streamed.equals(mostFrequentWord)) {
            counter++;
        } else if (counter == 0) {
            mostFrequentWord = streamed;
            counter = 1;
        } else {
            counter--;
        }
    }
    System.out.println(mostFrequentWord);
}
person assylias    schedule 18.07.2012
comment
Спасибо за помощь! Большое спасибо! Я думал, что попал в тупик! - person GG GG; 18.07.2012
comment
Я не верю, что это работает, похоже на мусор. Попробуйте против a a b b b a a, я полагаю, что ответ будет b, потому что он забывает о первых двух a, когда переключается на b, верно? Вы серьезно не можете сделать это, не зная истории (помните каждое отправленное слово и счет), но если я ошибаюсь в этом, я хотел бы знать, как... Кажется, чем старше я становлюсь, тем чаще я обращаюсь ошибаюсь в вещах, в которых я абсолютно уверен. - person Bill K; 19.07.2012
comment
@BillK Прежде чем говорить, что это мусор, вы должны проверить свои выводы. Использование a a b b b a a в качестве входных данных возвращает a, как и ожидалось (если вы не верите в это, это довольно легко проверить, изменив код и запустив его). - person assylias; 19.07.2012
comment
@BillK Вы должны проверить дубликат для полного объяснения того, как работает алгоритм. В частности, этот ответ: stackoverflow.com/a/3740548/829571 для отличного визуального объяснения. - person assylias; 19.07.2012
comment
@BillK Обратите внимание, что алгоритм работает только в том случае, если один из элементов появляется более 50% времени. Например, если у вас есть 3 элемента, которые появляются 30%, 30% и 40% времени, результат не определен. - person assylias; 19.07.2012
comment
Ладно, извини, это работает. Видишь, я говорил тебе о том, что в последнее время часто ошибался :) - person Bill K; 19.07.2012