смотря что Jin X назвал словом.
'мое дерево' хранит WORD
| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Быстрый поиск |
| Автор: Jin X 20.09.03, 08:55 |
| Имеется очень большой массив слов. Необходимо определить - есть ли в нём повторяющиеся слова (эти слова могут находиться в любом месте, даже в противоположных концах массива). |
| Автор: wormball 20.09.03, 08:57 |
| сортируй! я думаю за линейное время всё равно не получится |
| Автор: MeG 20.09.03, 10:11 |
| Если порядок данных в массиве не имеет значения, построй такое дерево: Узел содержит два указателя (и все) Глубина --- шестнадцать уровней (от 0 до 15) Нижний, пятнадцатый, уровень может указывать на терминатор (такой же узел, но указатели в нем всегда NULL, NULL) Каждое число --- это цепочка указателей от вершины дерева до терминатора. Количество узлов в полном (все 65536 вариантов) дереве 216, объем занимаемой памяти 2 * 216 указателей. Когда заносишь код который уже существует в дереве, обнаружишь что есть все указатели вплоть до терминатора. Время определения фиксированно, зависит от глубины дерева и не зависит от количества данных в дереве. |
| Автор: wormball 20.09.03, 10:16 |
| непонял какое отношение сие дерево имеет к задаче |
| Автор: MeG 20.09.03, 10:54 | ||
Быстрый поиск |
| Автор: wormball 20.09.03, 10:57 |
| ну ты умный! заголовок прочитал, а пост нет. задача то в том, чтобы определить, есть ли в массиве одинаковые слова. к тому же твоё древо будет искать не быстрее, чем двоичный поиск |
| Автор: MeG 20.09.03, 11:29 |
| В задаче не указано откуда беруться данные в массиве и как используется массив кроме поиска. Время поиска по 'моему' дереву фиксированное и не зависит от количества элементов в нем. |
| Автор: wormball 20.09.03, 11:40 |
| зато максимальное количество елементов в нём зависит от его глубины ;D так что как ни крути, qsort+двоичный поиск быстрее |
| Автор: MeG 20.09.03, 11:51 | ||
(хрум) ;D от глубины зависит разрядность хранимых данных |
| Автор: wormball 20.09.03, 11:58 |
| темболее!! строки-то большие!!какправило ;D |
| Автор: MeG 20.09.03, 12:13 |
| смотря что Jin X назвал словом. 'мое дерево' хранит WORD |
| Автор: wormball 20.09.03, 12:14 |
| ну в таком случае если в массиве больше чем 65536 слов, тогда и думать нечего - как пить дать одинаковые будут ;D |
| Автор: MeG 20.09.03, 12:24 |
обычные словари русского языка содержат еще меньше слов  |
| Автор: wormball 20.09.03, 12:27 |
| зато большой разрядности ;D |
| Автор: MeG 20.09.03, 12:35 |
| можно построить 'мое дерево' и для русских слов (или не русских ) и глубину не фиксировать, но игра стоит свеч только если "скорость превыше всего" |
| Автор: wormball 20.09.03, 12:38 |
| помоему наоборот, так двоичным поиском быстрее |
| Автор: MeG 20.09.03, 13:01 |
| я же говорю, скорость поиска не зависит (совсем!) от количества так думаю нагляднее  |
| Автор: wormball 20.09.03, 13:14 |
| ну так правильно, с помощью твоего дерева можно выразить только числа не больше ворда, а русские слова куда больше, придётся глубину увеличивать. |
| Автор: wormball 20.09.03, 13:23 |
| к тому же можно обойтись вобще без дерева. заводим массиф [0..65535] оф боолеан, ну и сей боолеан будет обозначать присутствие данного ворда в исходном массиве. так время поиска вобще не будет зависеть от колва данных (при етом сократится до трёх операций: индексации, обращения к памяти и сравнения), да и памяти в десятки раз (особенно если биты использовать) меньше потребуется. только чтобы все русские слова выразить всё равно много памяти уйдёт. |
| Автор: Demo_S 20.09.03, 16:46 |
| используй хеш-функцию. заводишь массив хешей. каждый элемент этого массива - ссылка на список элементов, имеющих такой хеш. проходим по массиву, если хеш для очередного слова совпал с каким-то ранее вычисленным хешем, то сравниваем это слово со всеми словами из списка. в худшем случае время конечно квадратичное. но появление такого случая маловероятно. в общем случае время приближается к линейному. (ведь нам надо только определить, есть ли повторения? первое же повторение - и выходим) и пример. хеш - первая буква слова хеш-массив а,б,в,г,д, ... (ну числе ессно, )for(int i=0;i<N;i++) { if(hash[array[i][0]]!=0) { list_pointer* lp=hash[array[i][0]]; while(lp) { if(strcmp(lp->data,array[i])==0) goto out; lp=lp->next; } } } естественно, что хеш функция должна быть получше. а хеш массив побольше. как пример хеш-функции - что-нить на тему суммы элементов. возможно не всех элементов, а только первого, среднго и последнего. |
| Автор: MeG 21.09.03, 07:52 |
дерево для словаря строим так   Чем больше слов в дереве, тем эффективнее используется память. Для русского (33 буквы) словаря из 60 тысяч слов, по ориентировочной оценке, потребуется около 5000 узлов, требуемый объем памяти менее 1,5 МБайт. Этот же словарь в виде массива займет, примерно, 600кБайт. В этом же дереве можно хранить и словарь английских слов, добавляем еще один терминатор и по другому интерпретируем связи. Дополнительные затраты будут мизерными. Еще раз. Время поиска по такому дереву не зависит от количества слов в нем, и зависит от длины слова. Очевидно, что вариантов решения может быть много. И известна старая проблема: если мы сокращаем затраты памяти, то увеличивается время обработки, Если уменьшаем время обработки, то возрастают затраты памяти. Каждый выбирает сам, что ему больше подходит. 2 Jin X, ты где пропал, открой секрет, что тебе нужно? |
| Автор: MeG 21.09.03, 18:29 | ||
| Jin X молчит как партизан продолжу в узлы нужно добавить признак конца слова, для разных языков разные флаги  Динамически выделять память для каждого узла не выгодно: дополнительные затраты памяти, потери времени для нескольких тысячь new/delete (или что там вам больше нравится), алгоритм удаления всего дерева сложный. Проще и быстрей выделить память для всего дерева сразу, удалять одним махом, или статически. что-то в этом духе
|
| Автор: S.Yu.Gubanov 22.09.03, 07:19 |
| Цитата MeG, 21.09.03, 11:52:34 дерево для словаря строим так  Круто! Я раньше где-то о таком слышал, но тогда не врубился. |
| Автор: wormball 22.09.03, 13:10 |
| всёравно в данной конкретной задаче quicksort работает быстрее. если уж ты не веришь моим словам, можно поспорить: я напишу qsort, ты напишешь дерево, jin x предоставит массив и мы посмотрим, кто быстрее. а потом я объясню, почему. ;D зы. желательно на паскале |
| Автор: Jin X 22.09.03, 16:41 |
| Ого! Имеется в виду поиск одинаковых слов в словаре русских и иностранных слов. Задача 1: удалить совпадения. Задача 2: быстро найти слово. 2 MeG: Интересный метод, но у него есть один недостаток: в твоё дерево нельзя заложить, например, слова "мир" и "мираж". Но если его немного модифицировать: добавить булевскую переменную "ТакоеСловоЕсть", то всё будет пучком. А вот памяти это будет жрать много, т.к. представь: есть, например, слово "компьютер"... ветвь, идущая от буквы "е" будет содержать 33 указателя (по 4 байта, даже по 5, если добавить bool), хотя использоваться будет только один. 2 wormball: Кол-во слов в словаре может быть несоклько сот тысяч. Для 200000 слов бинарный поиск будет достигать 18 итераций (сравнение + арифметические операции). Тормозным моментом здесь является создание хэшей (один раз для всего словаря) или сравнение целого слова (если не строить хэши). В методе MeG'а тормозным моментом является выделение памяти под каждое слово и инициализация таблицы указателей (но это тоже только 1 раз для всего словаря). Но твой метод менее ресурсоёмок. Ты всё-таки объясни, почему твой метод быстрее... Вообще, я надеялся, что можно как-нибудь организовать это дело (решение задачи 1) так, чтобы не искать каждое слово в словаре. Но это тоже неплохо. Всем спасибо! |
| Автор: wormball 22.09.03, 16:54 |
| моим методом искать слово не придётся. надо будет просто после сортировки просматривать подряд массив и удалять слово, если оно такое же, как идущее до него. я тут подумал и решил, что если букв больше 2х, то метод mega всётаки должен быть побыстрее. но всёже я думаю стоит сравнить в натуре. ивобще у моего метода сложность n log n, а у mega n log m, где m - колво букв в слове. |
| Автор: Jin X 22.09.03, 18:52 |
| Цитата wormball, 22.09.03, 20:54:31 Ты хотел сказать n*m ? а у mega n log m, где m - колво букв в слове |
| Автор: MeG 22.09.03, 19:20 |
| 2 wormball давай сравним ;D до выходных подождешь? для начала словарь один. (где ты там n нашел ?) 2 Jin X я сказал о флагах в 21 сообщении |
| Автор: wormball 23.09.03, 12:53 |
| Цитата Jin X, 22.09.03, 22:52:22 Ты хотел сказать n*m ? скорее да, чем нет я тут на досуге подумал ;D и решил, что у моего метода (т е у qsorta) будет m*n*log(n), ибо при сравнении строк в худшем случае придётся произвести m операций. похоже мне придётся признать своё поражение ;D |
| Автор: Jin X 25.09.03, 13:56 |
| Цитата MeG, 22.09.03, 23:20:46 Sorry, упустил.2 Jin X я сказал о флагах в 21 сообщении 2 wormball: Это уже "Память vs Скорость". Большая ли у вас с MeG'ом разница в скорости будет? |
| Автор: wormball 25.09.03, 14:15 |
| мерять надо! ведь n сравнений (особенно с cmpsb) и n переходов по ссылке - не одно и то же! похоже всётаки придётся написать qsort. только на с++е мне чото не хочется писать, да и в сети qsortов полно, и помнится в стандартной библиотеке qsort есь. остаётся написать только то, что должно быть после сортировки, т е собственно выбрасывание одинаковых строк. если не знаешь, как ето сделать без одалживания памяти - я тебе напишу, только надо будет знать, в каком формате строки. |
| Автор: Visitor 25.09.03, 14:45 |
| А если весь массив со строками существенно больше, чем размер доступной оперативной памяти? У MeG метод более универсальный P.S. Еще можно вспомнить алгоритм сжатия LZW -- структуру словаря етого алгоритма |
| Автор: wormball 25.09.03, 14:58 |
| Цитата Visitor, 25.09.03, 18:45:05 А если весь массив со строками существенно больше, чем размер доступной оперативной памяти? У MeG метод более универсальный вопервых если массив не умещается в память, то даже и думать нечего, а вовторых уменя насколько я понимаю меньше памяти тратится. Цитата Visitor, 25.09.03, 18:45:05 P.S. Еще можно вспомнить алгоритм сжатия LZW -- структуру словаря етого алгоритма тыбы ещё рар предложил ;D |
| Автор: Visitor 25.09.03, 15:32 |
| Вот RAR, с его алгоритмом LZ, как раз не подойдет А словарь-дерево из LZW или такое как у MeG, в случае слов естественного языка большим не будет. Вот представь себе такую задачу: некое собрание сочинений (например, Билиотека Мошкова) в електронном виде. Нужно из него сделать список всех форм всех имеющихся там слов русского языка. Читать слова придется из какого-то потока, а хранить словарь можно и в памяти. Хотя я бы, в етом случае, хранил слова просто в балансированном двоичном дереве. |
| Автор: Jin X 26.09.03, 19:37 |
| В LZW происходит то же самое: сравнение слова со всеми словами из словаря. К тому же, я что-то не совсем понимаю, какое LZW имеет отношение к делу. 2 wormball: qsort, создание дерева и т.п. нужно использовать только 1 раз, в самом начале. Так что, если qsort будет быстрее создания дерева, а двоичный поиск медленнее создания дерева (а мне почему-то кажется, что именно так и будет), то что быстрее - нужно рассчитывать уже по кол-ву поисков. |
| Автор: wormball 29.09.03, 05:57 |
| Цитата Jin X, 26.09.03, 23:37:42 Так что, если qsort будет быстрее создания дерева, а двоичный поиск медленнее создания дерева (а мне почему-то кажется, что именно так и будет), то что быстрее - нужно рассчитывать уже по кол-ву поисков. ещё раз объясняю: двоичного поиска не будет! после сортировки надо будет за линейное время сравнивать слова с идущими за ними словами. |
| Автор: Jin X 01.10.03, 17:25 |
| Да, точно... прогон Но тогда при поиске (не совпадений, а просто слова) будет |
| Автор: MeG 05.10.03, 17:55 |
| подведем итоги обсуждения предложенные методы поиска и удаления дубликатов:
Предлагаю сравнить все эти методы живьем. Смысл? Оценить предложенные методы с различных сторон. Требования к реализации достаточно свободные, любой язык, любые библиотеки. В общем, можно использовать все что вам доступно и удобно, в том числе готовые решения. Проверяем на одном словаре. Оцениваем:
Jin X, wormball, Demo_S, Visitor прошу участвовать |
| Автор: wormball 06.10.03, 13:20 |
| как всё сложно ;D |
| Автор: MeG 07.10.03, 19:32 |
| я грубо ошибся при оринтировочной оценке требуемого количества узлов в моем дереве для словаря, размер намного больше. если кому нужен исходник, вышлю |
| Автор: Sazabis 08.11.03, 00:02 |
| если всеравно что использовать, может попробуешь Perl, у него единица языка - слово. Для определения одинаковых слов очень подходит. Производительность высокая, можешь сравнить со своей производительностью, результаты были бы интересны  пишется на перле для такого дела всего несколько строчек |
| Автор: Visitor 08.11.03, 20:50 |
| Ну вот ориентировочные результаты: с помощью обычного (не балансированного) двоичного дерева из 100M текстов RFCxxxx словарь (слова состоящие из символов, у которых isalpha != 0) строится 17 сек на PIII-700 |
| Автор: Sazabis 10.11.03, 09:45 | ||||
код на Perl, без какой либо оптимизации правда, читает прямо из файла файл - текстовый - слова с пробелами. Слово это то, что ограничено пробелами или концом-началом строки.
Это собственно вся сортировка если бы каждое слово было на новой строчке было еще быстрей. А так как видно еще перебор каждой строки происходит. 2Visitor сравните, будет, конечно, не 17 сек, но результат интересен. запускается как perl название_скрипта файл_для_сортировки_без_расширения входной файл подразумевается .txt |
| Автор: Visitor 10.11.03, 10:57 | ||
rfcs.txt: 107 857 600 bytes
Тоже недолго... Вот только памяти он почему-то 120M сожрал в прцессе выполнения??? |
| Автор: Sazabis 10.11.03, 11:20 |
| Да память он любит, я тоже заметил. 2.16 неплохо, если память под массивы выделить сразу на все эл-ты, и сделать так, что слово есть 1 строчка. Можно будет еще время выграть, но это уже для фанатов. |
| Автор: Misha_Muhin 14.11.03, 18:50 |
| думаю,надо взять хеш,делающий из слова первые его 8 байт. время-линейное на хеш, const на нахождение нужного ключа в среднем порядка n на нахождение эл-та(по моим прикидкам) |
| Автор: Visitor 14.11.03, 19:13 |
| Из первых восьми, наверное, маловато будет... Много слов естественного языка одинаково начинаются. Кстати, повод для новой темы |
| Автор: RoboTact 27.12.04, 10:47 |
| Цифровая сортировка отдыхает... |