Задача. Есть большой текстовый файл (15Мб). Нужно найти в нем повторения. Ваш способ?

интернет компьютеры программирование алгоритм формат

Вопрос явно не для "чайников" :-)

Известно, что повторений не много (не более 30). Все строки в файле однотипны - т.е. файл является своего рода логом специфических событий (дата, время, название события, продолжительность события, результат события и т.п.). Длина сравниваемых фраз не короче 5 символов. Ручной поиск невозможен по причине большого объема данных. Как бы вы искали?

Примечание:
во первых - ОС Win XP, во вторых пример куска файла, чем поможет Ваша сортировка в данном случае? не очень понимаю:

01.01.2010 00:01:00 - Свисток паровоза - 00:10 - удачно
01.01.2010 00:01:05 - Начало движения паровоза - 01:05 - удачно
01.01.2010 00:02:00 - Торможение паровоза - 00:15 - неудачно
01.01.2010 00:03:00 - Прибытие паровоза в пункт назначения - 02:10 - удачно
01.01.2010 00:04:00 - Свисток паровоза 00:10 удачно

Примечание:
alexander.p - речи вообще не шло о "сравнении строк" - сравниваются именно "фразы" (слова, или группы слов) длиной от 5 символов. так в примере мне нужно было бы найти "Свисток паровоза" - так как он указан дважды.

Примечание:
alarmeria - вы правы, в примере "паровоза" тоже как то много. на выходе ... что на выходе? например файл в котором парами указаны строки, в которых есть фразы-повторения определенной длины. Хотя определенной длины тоже не получится, потому что искомые фразы могут быть длиной от 5 до 8 символов...
Ответы:
cat file.txt |sort |uniq -d
notepad++ легко справится с поиском по большому файлу.
Про скриптинг... Написал бы на php скрипт. В принципе довольно быстро бы отработал 15 мб.
Как я бы сделал: цикл по всему файлу, смотрим подстроки из 5 символов, для каждой берём хэш и запоминаем. Получаем места коллизий, если хэш хороший, их не сильно много. А дальше просто проверяем для каждого места
Вы сформулируйте точно, что считаете фразой. Станет понятно, что делать.
сортировка тут не поможет в явном виде, так как у вас первые значения это дата - время, поэтому как указывали товарищи выше придется писать скрипт на perl (он есть и под windows) либо писать программу на какомто другом языке, а так возможен следующий алгоритм:
поменять порядок полей (с помощью опять же скрипта, можно даже на командном языке CMD, при условии наличия разделителей полей например символ "#"
или вообще отбросить все неучитываемые поля, затем сортировка и сравнение по повторам... хотя конечно не известно нужна ли вам эта информация в ваших дублях...
Итак, если формально:
"слово" - последовательность букв, ограниченная пробелами
"фраза" - последовательность слов, включающая >= 5 символов
Так?
Если так, то работаем по следующему алгоритму:
1. Строим дерево. В каждой вершине записана буква. Каждой вершине соответствует слово, получающееся прохождением от вершины до корня (корень - пустое слово). Нумеруем активные вершины int'ами - на это все требуется время, линейное по размеру файла.
2. Каждому слову таким образом соответствует число (по числу восстанавливается и слово, и длина). Заменяем строки на последовательности чисел. В каждой строке находим все минимальные последовательности слов, длины которых >=5 (последовательность называется минимальной, если у нее нет собственной подпоследовательности длины >=5). Записываем все такие фразы в виде дерева. Тут уже нужно строить сбалансированное дерево с вершинами. В каждой вершине, помимо числа (номера слова) либо указатель на поддерево, в котором искать следующее слово, либо список фраз, в которых есть такая последовательность (если уже дошли до достаточной длины).
3. Проходимся по этому "дереву деревьев". Для вершин, в которых написано, что фраза встречается в >= 2 строчках, восстанавливаем, что это за фраза и в каких она строчках.
Естественно, это надо писать на чем-то нормальном, вроде перла/пифона/пхп, а если это надо делать еще и быстро - то С++ наше все.
cut и uniq
Да ты еше себя назвал ВЫСШИЙ РАЗУМ где твой высший разум ХДД


15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.