Поиск элемента, который встречается чаще всего в очень большом файле

12

Я слышал, что этот вопрос задавался много раз, и я надеялся получить какое-то мнение о том, какие могут быть хорошие ответы: у вас большой файл размером более 10 ГБ, и вы хотите выяснить, какой элемент встречается чаще всего, какой способ лучше сделать это?

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

Другие мысли, которые я включил в разделение файла, который будет повторяться и обрабатываться несколькими потоками, а затем объединять эти результаты, но проблема с памятью для карт все еще остается.

похлопывание
источник
2
Каковы элементы файла? Это струны? Если вы берете символы за элементы, то у карты не будет проблем с памятью. Если элементы являются словами, то, опять же, я думаю, что это не будет проблемой. Если у вас есть все возможные подстроки, то у вас могут быть проблемы ...
Nejc
1
Если бы условие было «элементом, который появляется больше, чем половина всех элементов», тогда было бы линейное решение.
st0le
Я считаю, что элементы обычно являются строками. Но я не вижу, как карта не проблема. В худшем случае, когда каждый элемент уникален, разве вы не удвоили свои требования к памяти?
Пэт
1
Если применим алгоритм кандидата большинства Бойера-Мура, он работает за линейное время и находится на месте.
Юхо

Ответы:

6

Когда у вас есть действительно большой файл и много элементов в нем, но самый распространенный элемент очень распространен - ​​встречается доли времени - вы можете найти его в линейном времени с пробелом слов ( Константа в нотации очень мала, в основном 2, если вы не учитываете память для вспомогательных вещей, таких как хеширование). Более того, это прекрасно работает с внешним хранилищем, поскольку файл обрабатывается последовательно по одному элементу за раз, и алгоритм никогда не «оглядывается назад». Один из способов сделать это - использовать классический алгоритм Мисры и Гриса, см. Эти лекционные заметки . Проблема теперь известна как проблема тяжелых нападающих (частые элементы - тяжелые нападающие).O ( k ) O ( )>1/kO(k)O()

Предположение, что наиболее частый элемент появляется доли времени для небольшого числа, может показаться сильным, но это необходимо! Т.е., если у вас будет последовательный доступ к вашему файлу (и в случае, если файл огромен, произвольный доступ будет слишком дорогим), любой алгоритм, который всегда находит наиболее частый элемент за постоянное число проходов, будет использовать пространство, линейное по количеству элементов. , Поэтому, если вы не предполагаете что-то о вводе, вы не можете разбить хеш-таблицу. Предположение, что наиболее частый элемент является очень частым, возможно, является наиболее естественным способом обойти отрицательные результаты.к>1/kk

Вот набросок для , то есть когда есть один элемент, который встречается более половины времени. Этот особый случай известен как алгоритм большинства голосов и связан с Бойером и Муром. Мы будем хранить один элемент и один счет. Инициализируйте счетчик до 1 и сохраните первый элемент файла. Затем обработайте файл в последовательности:k=2

  • если текущий элемент файла совпадает с хранимым элементом, увеличьте число на единицу
  • если текущий элемент файла отличается от хранимого элемента, уменьшите счет на единицу
  • если обновленный счетчик равен 0, «выкинуть» сохраненный элемент и сохранить текущий элемент файла; увеличить счет до 1
  • перейти к следующему элементу файла

Немного подумав об этой процедуре, вы убедите вас в том, что если существует элемент «большинства», то есть тот, который встречается более половины времени, то этот элемент будет сохраненным элементом после обработки всего файла.

Общих , вы держите элементы и рассчитывает, и инициализировать элементы к первому различных элементам файла и рассчитывает на количество раз , каждый из этих элементов появляется , прежде чем вы видите -й отличный элемент. Затем вы запускаете, по сути, ту же процедуру: счетчик элемента увеличивается каждый раз, когда он встречается, все счетчики элементов уменьшаются, если встречается элемент, который не сохранен, и когда некоторое количество равно нулю, этот элемент исключается в пользу текущий элемент файла. Это алгоритм Мисры-Гриса.k - 1 k - 1 k kkk1k1kk

Конечно, вы можете использовать хеш-таблицу для индексации хранимых элементов. При завершении этот алгоритм гарантированно возвращает любой элемент, который встречается более чем в доле времени. По сути, это лучшее, что вы можете сделать с алгоритмом, который делает постоянное количество проходов по файлу и сохраняет только слов.1 / k O ( k )k11/kO(k)

И последнее: после того, как вы нашли кандидатов в «сильные нападающие» (то есть частые элементы), вы можете сделать еще один проход по файлу для подсчета частоты каждого элемента. Таким образом, вы можете ранжировать элементы между собой и проверить, все ли они встречаются более чем в доле времени (если таких элементов меньше, чем , некоторые из элементов, возвращаемых алгоритмом, могут быть ложноположительными ).1kk - 11/kk1

Сашо Николов
источник
Вы не можете использовать алгоритмы Бойера-Мура или Мисры-Гриса-Демейна. Проблема, как указано, отличается: вы ищете не элемент большинства, а элемент, вхождения которого> = вхождений всех элементов. Вот простой контрпример. Пусть n будет общим количеством элементов, таким, что n = 2k + 1 . Пусть первые k элементов равны 0, следующие k элементов равны 1, а последний элемент равен 2. Алгоритм Бойера-Мура сообщит о последнем элементе 2 как потенциальном кандидате в большинство. Но для этого конкретного случая выходной сигнал должен быть либо 0, либо 1.
Massimo Cafaro
@MassimoCafaro Я не могу разобрать фразу "чьи случаи ... элементы". В любом случае, общеизвестно, что для нахождения наиболее частого элемента в требуется памяти! поэтому, если вы хотите небольшой отпечаток памяти, вам нужно сделать дополнительное предположение, предположение о сильном нападающем является наиболее естественным для меня. Ω ( n )O(1)Ω(n)
Сашо Николов
Я только что указал, что если вы сделаете неправильное предположение, вы можете получить неправильные результаты. Что лучше: маленький объем памяти и потенциально неправильный результат или правильный результат, даже если это стоит вам больше памяти? Если бы мне пришлось выбирать потенциально неверный результат, я бы использовал рандомизированный алгоритм, а не Бойера-Мура, предполагая что-то, чего я не знаю, что это действительно так.
Массимо Кафаро
@MassimoCafaro, который не является компромиссом, который вам нужно принять. как я уже говорил, один проход по файлу легко проверяет, выполнено ли предположение!
Сашо Николов
@MassimoCafaro и это только тривиальное решение! предположение может быть подтверждено с высокой вероятностью с помощью эскиза КМ без дополнительных проходов.
Сашо Николов
3

Очевидный ответ, конечно, состоит в том, чтобы сохранить хэш-карту и сохранить счетчик появления элементов при перемещении по файлу, как уже предлагал Нейц. Это (с точки зрения сложности времени) оптимальное решение.

Однако, если ваши требования к пространству жесткие, вы можете выполнить внешнюю сортировку файла, а затем найти самый длинный последовательный прогон равных элементов. Следующее должно иметь постоянный объем памяти и может быть сделано вΘ(nlogn).

Jernej
источник
Не могли бы вы подробнее рассказать о подходе кодирования Хаффмана? Я уже писал кодировщик Хаффмана, но прошло какое-то время, как именно вы бы использовали его в этом случае?
Пэт
@Pat Неважно, что это было слишком рано утром, и почему-то я подумал, что имеет смысл сжимать ввод.
Jernej
1

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

adrianN
источник
Более того, если имеется небольшое количество элементов, встречающихся много раз, вы можете найти их путем выборки, а затем точно считать только эти элементы.
Макс.