Xpoint
   [напомнить пароль]

Совпадения в файле

Метки: [без меток]
[удл]
2005-05-10 20:45:46 [обр] d2rk(0/23)[досье]
Как можно получить $n колличество повторяющихся строк болького файла? И как открыть такой файл, если его размер "ну очень" большой?
спустя 14 минут [обр] Владимир Палант(27/4445)[досье]

Файл, независимо от размера, открывается очень просто: open(FILE, $filename) :)

Что касается первого вопроса, то нельзя ли более точно описать задачу? Требуется найти строку, повторяющуюся максимальное количество раз? Или определить количество повторений для каждого значения строки? По-моему, и то, и другое потребует большого количества памяти, если файл "ну очень большой" — или его придётся читать много раз.

спустя 17 часов [обр] d2rk(0/23)[досье]
Что касается $n, то она содержит максимальное количество часто повторяющихся строк.
А относительно открытия "ну очень" большого файла, я считаю, что открывать файл размером более 1Гб просто с помощью
open(FILE, $filename), не очень удобно. Я предлагаю считывать ,хотя бы, по 10Мб из файла, при этом записывая это в массив, для более корректной и простой обработки информации.
спустя 54 минуты [обр] Владимир Палант(27/4445)[досье]

Вы понимаете, что между открытием файла и считыванием данных из него существует немалая разница?

Если решать вашу задачу с абсолютной точностью, то придётся либо израсходовать 1Гб памяти, либо сделать несколько проходов по файлу (к примеру, если делать четыре прохода, то хватит четверти памяти). Не думаю, что такое решение вас устраивает. Может вас устроит приблизительное решение, которое в большинстве случаев выдаст правильный или хотя бы близкий к нему результат?

Вариант:

  1. Читать файл блоками по 10000 строк.
  2. Для каждого блока считать, сколько раз какая строка в нём встречается (хеш строка => количество).
  3. Из результата по блоку выкинуть всё, кроме десяти самых распространённых строк. Только эти самые распространённые строки добавить в результат по всему файлу (такой же хеш).
  4. Когда все блоки прочитаны, найти в хеше распространённости для всего файла строку с максимальным количеством и выдать её.

Точность не абсолютная и существует даже вероятность выдать не самую распространённую строку. Но приближение не слишком плохое и расход памяти предсказуем — максимум порядка одной тысячной от размера всего файла.

Думаю, не перенести ли этот вопрос в Программирование::Теория и Алгоритмы.

спустя 1 день 2 часа [обр] d2rk(0/23)[досье]

Разницу между открытием файла и считыванием из него данных я понял, спасибо. Данный способ очень удобен и прост, хотя могут быть и погрешности, и результат будет не точным (как Вы и говорили). Но я бы внес некоторые изменения:

С первым и вторым пунктами я согласен, хотя во втором пункте вместо (хеш строка => количество) поставить (хеш сжатая строка => количество).

Сжатой строке присваивается какое-либо символьное обозначение (можно и без этого, просто пояснение), а в пояснение – все первые буквы слов с учетом регистра.

Третий пункт не включает в себя удаления десяти самых распространённых строк, так как сжатая стока не будет расходовать много памяти, поэтому все обработанные строки можно оставить.

По мере обработки блоков при совпадении ‘сжатых строк‘ хеша, объединять их, а их ‘количество‘ складывать.

Четвертый пункт. Из конечного хеша получаем количество повторений строк в файле.

Насчет точности и корректности работы я не уверен, но процент найти наиболее часто повторяющиеся строки может увеличиться.

# хотя во всех случаях всё зависит от количества памяти. Если у кого-то ее более чем 1Гб то пожалуйста, можно открыв файл сразу считывать все в хеш, а так можно подгонять скрипт под размеры памяти.

спустя 1 час 45 минут [обр] Владимир Палант(27/4445)[досье]
Если выкинуть третий пункт, то получится тривиальный точный алгоритм с нулевой экономией памяти (то есть экономия исключительно за счет совпадающих строк и "сжатия", worst-case: расход памяти совпадает с размером файла). И тогда нет смысла использовать несколько хешей, хватит одного, для конечного результата. Из вашей постановки вопроса я понял, что такой вариант вас не устраивает — ошибся, видимо.
спустя 3 дня [обр] d2rk(0/23)[досье]
Владимир Палант, можете ли Вы реализовать свою идею на примере?
спустя 2 дня 5 часов [обр] Владимир Палант(27/4445)[досье]

Что вы имеете в виду? Кажется, вы неправильно поняли мой последний постинг, он касался вашего изменения алгоритма и его последствий — на мой взгляд, результат получается неудовлетворительный.

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

спустя 3 дня [обр] d2rk(0/23)[досье]
Спасибо, я просто поинтересовался. А реализовать ваш алгоритм я могу и сам.
спустя 6 лет [обр] Евгений Седов aka KPbIC(0/187)[досье]
М Перенесено из форума "Программирование::Perl::Разное"
Powered by POEM™ Engine Copyright © 2002-2005