Удаление дублей

Можно сделать при помощи PHP скрипта. Просто нужно его написать правильно. Одна проблема, он будет работать долго и алгоритм "хитрый" нужен. Тут есть над чем подумать минут 20-30 :) Один из вариантов (наверное самых НЕоптимальных) - это: открыть файл > прочитать 100 строк в массив > очистить эти 100 строк от совпадений > читать весь файлы кусками (выбрать лучший вариант чтения: по 1 строке, по 100 строк и т.д.) и проверять на совпадения > удалять совпадения > записать строки без совпадений во временный файл > заменить файл из которого читали временным >> прочитать в массив следующий 100 строк и т.д.

WebProgrammer добавил 30.11.2008 в 22:05

Ну можно еще сюда сходить http://www.rusdocs.com/text-duplicate-killer-utilita-dlya-udaleniya-iz-spiska-povtoryayushhixsya-strok

Кто напишет? Программа хорошая, но там нужно выбирать по одному файлу. А мне желательно что бы удаление дублей было сразу по всем. Также, если дубли присутствуют например в первом и восьмом файлах - они тоже удалялись.

Циклом читать по строке из файла, высчитывать md5 для строки и добавлять в таблицу MySQL. Перед вставкой проверять на наличие такого же кода. Если есть - дубль.

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

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

Скрипт совсем простенький получится, если с БД проблем нет.

Ну вот. Осталось только что б кто-то написал :)

5 wmz на пиво хватит?

На фрилансе каком-нибудь можно запостит, думаю за $5 найдутся желающие. Там работы минут на 20-30.

Давай я напишу, если надо еще.

за пять баксов ) Это смешно. Нужен хешированный поиск.

Берется функция H(строка S, int M), которая возвращает число не более M.

Потом создается M хеш-файлов-ссылок номер файла, номер строки, и М Хеш-Файлов содержаний. В файлах содержаний - содержания строки исходного файла. Строка записывается в хеш файлы под номерами равными ее хешу.

Потом происходит отбработка хеш файла. Строки сверяются и создается 50 очередей удаления (для каждого исходного файла) - они содержат номер строки который нужно удалить. Затем очереди обрабатываются.

М следует выбирать на 1-3 порядка меньшим числа строк. М должно быть простым числом. Время поиска дублей сокращается в M*M раз.

Можно ускорить введя CRC. Числа будут сверяться быстрее строк. Если CRC двух строк равны, то проверяются уже строки.

А чем KeyWordKeeper не устраивает? Там есть функция удаления дублей.

совпадение md5 не однозначно совпадению строк. Две разные строки могут иметь одинаковую контрольную сумму. Если размер кс не больше размеру строки )))). Нужно дополнительно сверять эти строки. Вторая строка у нас есть в памяти, но первая (мд которой уже есть в базе) находиться в довольно длином файле и в среднем нужно считать 1500/50/2 = 150 мб. чтобы добраться до него. Т.е. на одно удаление нужно считать минимум 150 мб. Это займет как минимум несколько секунд.

Второй момент - таблица. Найти мд в таблице - довольно сложно и эту операцию нужно произвести N раз. Где N число строк равное нескольким десяткам (а то и сотням) милионов.

НЕ знаю как Мускл организует таблицу. Но в самом оптимальном варианте (бинарный поиск или поиск по оптимально сбалансированному дереву) эта радость займет время пропорциональное ln(N). Т.е. N*Ln(N) - что очень плохо.

а не легче написать 10-строчный php скрипт, который потом запустить у себя на локалхосте с memory_limit в 2048 допустим?