Быстрый поиск

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

сортируй! я думаю за линейное время всё равно не получится

Если порядок данных в массиве не имеет значения, построй такое дерево:
 Узел содержит два указателя (и все)
 Глубина --- шестнадцать уровней (от 0 до 15)
 Нижний, пятнадцатый, уровень может указывать на терминатор (такой же узел, но указатели в нем всегда NULL, NULL)
 Каждое число --- это цепочка указателей от вершины дерева до терминатора.
Количество узлов в полном (все 65536 вариантов) дереве 2¹⁶, объем занимаемой памяти 2 * 2¹⁶ указателей. Когда заносишь код который уже существует в дереве, обнаружишь что есть все указатели вплоть до терминатора. Время определения фиксированно, зависит от глубины дерева и не зависит от количества данных в дереве.

непонял какое отношение сие дерево имеет к задаче

Быстрый поиск

Сообщение отредактировано: MeG - 07.11.03, 15:48

ну ты умный! заголовок прочитал, а пост нет. задача то в том, чтобы определить, есть ли в массиве одинаковые слова. к тому же твоё древо будет искать не быстрее, чем двоичный поиск

В задаче не указано откуда беруться данные в массиве и как используется массив кроме поиска.
Время поиска по 'моему' дереву фиксированное и не зависит от количества элементов в нем.

зато максимальное количество елементов в нём зависит от его глубины ;D
так что как ни крути, qsort+двоичный поиск быстрее

(хрум) ;D
от глубины зависит разрядность хранимых данных

Сообщение отредактировано: MeG - 07.11.03, 15:48

темболее!! строки-то большие!!какправило ;D

смотря что Jin X назвал словом.
'мое дерево' хранит WORD  

Сообщение отредактировано: MeG - 07.11.03, 15:49

ну в таком случае если в массиве больше чем 65536 слов, тогда и думать нечего - как пить дать одинаковые будут ;D

обычные словари русского языка содержат еще меньше слов

зато большой разрядности ;D

можно построить 'мое дерево' и для русских слов (или не русских ) и глубину не фиксировать, но игра стоит свеч только если "скорость превыше всего"

Сообщение отредактировано: MeG - 07.11.03, 15:49

помоему наоборот, так двоичным поиском быстрее

я же говорю, скорость поиска не зависит (совсем!) от количества

так думаю нагляднее

Сообщение отредактировано: MeG - 07.11.03, 15:50

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

к тому же можно обойтись вобще без дерева. заводим массиф [0..65535] оф боолеан, ну и сей боолеан будет обозначать присутствие данного ворда в исходном массиве. так время поиска вобще не будет зависеть от колва данных (при етом сократится до трёх операций: индексации, обращения к памяти и сравнения), да и памяти в десятки раз (особенно если биты использовать) меньше потребуется. только чтобы все русские слова выразить всё равно много памяти уйдёт.

Сообщение отредактировано: wormball - 20.09.03, 13:24

используй хеш-функцию.

заводишь массив хешей. каждый элемент этого массива - ссылка на список элементов, имеющих такой хеш.

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

и пример. хеш - первая  буква слова

хеш-массив
а,б,в,г,д, ...  (ну числе ессно, )

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;
             }

    }
}

естественно, что хеш функция должна быть получше. а хеш массив побольше.

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

Сообщение отредактировано: Demo_S - 20.09.03, 16:50

дерево для словаря строим так



Чем больше слов в дереве, тем эффективнее используется память. Для русского (33 буквы) словаря из 60 тысяч слов, по ориентировочной оценке, потребуется около 5000 узлов, требуемый объем памяти менее 1,5 МБайт. Этот же словарь в виде массива займет, примерно, 600кБайт.

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

Еще раз. Время поиска по такому дереву не зависит от количества слов в нем, и зависит от длины слова.

Очевидно, что вариантов решения может быть много. И известна старая проблема: если мы сокращаем затраты памяти, то увеличивается время обработки, Если уменьшаем время обработки, то возрастают затраты памяти.  Каждый выбирает сам, что ему больше подходит.

2 Jin X, ты где пропал, открой секрет, что тебе нужно?

Сообщение отредактировано: MeG - 07.11.03, 15:51

Jin X молчит как партизан

продолжу
в узлы нужно добавить признак конца слова, для разных языков разные флаги


Динамически выделять память для каждого узла не выгодно: дополнительные затраты памяти, потери времени для нескольких тысячь new/delete (или что там вам больше нравится), алгоритм удаления всего дерева сложный. Проще и быстрей выделить память для всего дерева сразу, удалять одним махом, или статически.

что-то в этом духе

Сообщение отредактировано: MeG - 07.11.03, 15:51

Цитата MeG, 21.09.03, 11:52:34

дерево для словаря строим так

Круто! Я раньше где-то о таком слышал, но тогда не врубился.

всёравно в данной конкретной задаче quicksort работает быстрее. если уж ты не веришь моим словам, можно поспорить: я напишу qsort, ты напишешь дерево, jin x предоставит массив и мы посмотрим, кто быстрее. а потом я объясню, почему. ;D

зы. желательно на паскале

Сообщение отредактировано: wormball - 22.09.03, 13:27

Ого!
Имеется в виду поиск одинаковых слов в словаре русских и иностранных слов.
Задача 1: удалить совпадения.
Задача 2: быстро найти слово.

2 MeG: Интересный метод, но у него есть один недостаток: в твоё дерево нельзя заложить, например, слова "мир" и "мираж". Но если его немного модифицировать: добавить булевскую переменную "ТакоеСловоЕсть", то всё будет пучком. А вот памяти это будет жрать много, т.к. представь: есть, например, слово "компьютер"... ветвь, идущая от буквы "е" будет содержать 33 указателя (по 4 байта, даже по 5, если добавить bool), хотя использоваться будет только один.

2 wormball: Кол-во слов в словаре может быть несоклько сот тысяч. Для 200000 слов бинарный поиск будет достигать 18 итераций (сравнение + арифметические операции). Тормозным моментом здесь является создание хэшей (один раз для всего словаря) или сравнение целого слова (если не строить хэши). В методе MeG'а тормозным моментом является выделение памяти под каждое слово и инициализация таблицы указателей (но это тоже только 1 раз для всего словаря). Но твой метод менее ресурсоёмок.
Ты всё-таки объясни, почему твой метод быстрее...

Вообще, я надеялся, что можно как-нибудь организовать это дело (решение задачи 1) так, чтобы не искать каждое слово в словаре.

Но это тоже неплохо.
Всем спасибо!

Сообщение отредактировано: 7in - 22.09.03, 16:45

моим методом искать слово не придётся. надо будет просто после сортировки просматривать подряд массив и удалять слово, если оно такое же, как идущее до него.

я тут подумал и решил, что если букв больше 2х, то метод mega всётаки должен быть побыстрее. но всёже я думаю стоит сравнить в натуре.

ивобще у моего метода сложность n log n, а у mega n log m, где m - колво букв в слове.

Сообщение отредактировано: wormball - 22.09.03, 17:00

Цитата wormball, 22.09.03, 20:54:31

а у mega n log m, где m - колво букв в слове

Ты хотел сказать n*m ?

2 wormball
давай сравним  ;D
до выходных подождешь?
для начала словарь один.
(где ты там n нашел ?)

2 Jin X я сказал о флагах в 21 сообщении

Цитата Jin X, 22.09.03, 22:52:22

Ты хотел сказать n*m ?

скорее да, чем нет

я тут на досуге подумал ;D и решил, что у моего метода (т е у qsorta) будет m*n*log(n), ибо при сравнении строк в худшем случае придётся произвести m операций.

похоже мне придётся признать своё поражение ;D

Цитата MeG, 22.09.03, 23:20:46

2 Jin X я сказал о флагах в 21 сообщении

Sorry, упустил.
2 wormball: Это уже "Память vs Скорость". Большая ли у вас с MeG'ом разница в скорости будет?

мерять надо! ведь n сравнений (особенно с cmpsb) и n переходов по ссылке - не одно и то же! похоже всётаки придётся написать qsort. только на с++е мне чото не хочется писать, да и в сети qsortов полно, и помнится в стандартной библиотеке qsort есь. остаётся написать только то, что должно быть после сортировки, т е собственно выбрасывание одинаковых строк. если не знаешь, как ето сделать без одалживания памяти - я тебе напишу, только надо будет знать, в каком формате строки.

А если весь массив со строками существенно больше, чем размер доступной оперативной памяти? У MeG метод более универсальный

P.S. Еще можно вспомнить алгоритм сжатия LZW -- структуру словаря етого алгоритма

Цитата Visitor, 25.09.03, 18:45:05

А если весь массив со строками существенно больше, чем размер доступной оперативной памяти? У MeG метод более универсальный

вопервых если массив не умещается в память, то даже и думать нечего, а вовторых уменя насколько я понимаю меньше памяти тратится.

Цитата Visitor, 25.09.03, 18:45:05

P.S. Еще можно вспомнить алгоритм сжатия LZW -- структуру словаря етого алгоритма

тыбы ещё рар предложил ;D

Вот RAR, с его алгоритмом LZ, как раз не подойдет

А словарь-дерево из LZW или такое как у MeG, в случае слов естественного языка большим не будет. Вот представь себе такую задачу: некое собрание сочинений (например, Билиотека Мошкова) в електронном виде. Нужно из него сделать список всех форм всех имеющихся там слов русского языка. Читать слова придется из какого-то потока, а хранить словарь можно и в памяти.

Хотя я бы, в етом случае, хранил слова просто в балансированном двоичном дереве.

Сообщение отредактировано: Visitor - 25.09.03, 15:33

В LZW происходит то же самое: сравнение слова со всеми словами из словаря. К тому же, я что-то не совсем понимаю, какое LZW имеет отношение к делу.

2 wormball: qsort, создание дерева и т.п. нужно использовать только 1 раз, в самом начале. Так что, если qsort будет быстрее создания дерева, а двоичный поиск медленнее создания дерева (а мне почему-то кажется, что именно так и будет), то что быстрее - нужно рассчитывать уже по кол-ву поисков.

Цитата Jin X, 26.09.03, 23:37:42

Так что, если qsort будет быстрее создания дерева, а двоичный поиск медленнее создания дерева (а мне почему-то кажется, что именно так и будет), то что быстрее - нужно рассчитывать уже по кол-ву поисков.

ещё раз объясняю: двоичного поиска не будет! после сортировки надо будет за линейное время сравнивать слова с идущими за ними словами.

Да, точно... прогон
Но тогда при поиске (не совпадений, а просто слова) будет

подведем итоги обсуждения

предложенные методы поиска и удаления дубликатов:

• сортировка + двоичный поиск
• MeGTree
• хеш-функция
• балансированное двоичное дерево
• прямой перебор

Предлагаю сравнить все эти методы живьем. Смысл? Оценить предложенные методы с различных сторон.
Требования к реализации достаточно свободные, любой язык, любые библиотеки. В общем, можно использовать все что вам доступно и удобно, в том числе готовые решения.

Проверяем на одном словаре.

Оцениваем:

• объем памяти занимаемый данными (в готовом к поиску состоянии)
• время подготовки структуры словаря к работе (исходный словарь берем из файла)
• время поиска заданного набора слов
• время уничтожения структуры словаря в памяти

и еще личная оценка сложности, универсальности ...


Jin X, wormball, Demo_S, Visitor прошу участвовать

Сообщение отредактировано: MeG - 07.11.03, 15:54

как всё сложно ;D

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

если всеравно что использовать, может попробуешь Perl, у него единица языка - слово. Для определения одинаковых слов очень подходит.
Производительность высокая, можешь сравнить со своей производительностью, результаты были бы интересны

пишется на перле для такого дела всего несколько строчек

Ну вот ориентировочные результаты: с помощью обычного (не балансированного) двоичного дерева из 100M текстов RFCxxxx словарь (слова состоящие из символов, у которых isalpha != 0) строится 17 сек на PIII-700

код на Perl, без какой либо оптимизации правда, читает прямо из файла файл - текстовый - слова с пробелами. Слово это то, что ограничено пробелами или концом-началом строки.

Это собственно вся сортировка
если бы каждое слово было на новой строчке было еще быстрей. А так как видно еще перебор каждой строки происходит.

2Visitor
сравните, будет, конечно, не 17 сек, но результат интересен.

запускается как perl название_скрипта файл_для_сортировки_без_расширения

входной файл подразумевается .txt

rfcs.txt: 107 857 600 bytes

Тоже недолго...

Вот только памяти он почему-то 120M сожрал в прцессе выполнения???

Сообщение отредактировано: Visitor - 10.11.03, 11:05

Да память он любит, я тоже заметил.

2.16 неплохо, если память под массивы выделить сразу на все эл-ты, и сделать так, что слово есть 1 строчка. Можно будет еще время выграть, но это уже для фанатов.

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

Из первых восьми, наверное, маловато будет... Много слов естественного языка одинаково начинаются.

Кстати, повод для новой темы

Цифровая сортировка отдыхает...