поиск слова из словаря в данных

[vv40in]

Желаю всем здоровья!

У меня такая задача :

Есть редко изменяемый словарь. В нём 50000 и более слов, длина слова ~100 символов.
Примечание. Строка здесь - это массив любых байтов.

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

Вопрос: какие существуют алгоритмы для токого поиска?
Вопрос не о поиске строки в строке (такие алгориты известны), а именно в поиске массива строк в строке.

Спасибо.

[ewert]

1) что токое "слово"? в частности, считается ли словом "фраза"?
2) что такое "строка? и что такое "массив строк"?
3) а что и где, собственно, ищется (если, например, конкретное слова из словаря, то при чём тут сортировка)?

[vv40in]

ewert писал(а):

1) что токое "слово"? в частности, считается ли словом "фраза"?

vv40in писал(а):

Примечание. Строка здесь - это массив любых байтов.

Слово = строка.

ewert писал(а):

2) что такое "строка? и что такое "массив строк"?

Строка = слово = массив любых байтов.
Т.о.Ваш пример - тоже строка. Даже вместе с кавычками
А что - это важно? По-моему для поиска это не существенно.
Массив строк - то же самое, что и словарь = набор,таблица строк(слов).

ewert писал(а):

3) а что и где, собственно, ищется (если, например, конкретное слова из словаря, то при чём тут сортировка)?

Надо найти в данных любое слово из словаря.

[ewert]

vv40in в сообщении #186081 писал(а):

Надо найти в данных любое слово из словаря.

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

vv40in в сообщении #186081 писал(а):

А что - это важно? По-моему для поиска это не существенно.

Существенно. Существуют ли символы-разделители?
Или Вам надо просто какой-то архиватор сочинить?

[Архипов]

ewert уже задал уточняющие вопросы.
Для vv40in :
**Укажите признаки слова.
1) Длина слова:
* фиксированная длина (например: 100 символов)
* слово любой длины заключено в пограничные уникальные символы (например [b.vv40in./b])
* слова, длиной не более 100, отделены друг от друга условным символом (пробелом, например).
2) Предел кода символов (32 либо 128 либо 256)

**Укажите признаки массива слов:
1) Массив задан иерархией фиксированных количеств слов фиксированной длины в разделах, подразделах, ...(например СЛОВАРЬ(24,15,7)).
2) Массив задан иерархией уникальных Заголовков в разделах (например: СЛОВАРЬ(Раздел1(подразел1,подраздел2), Раздел2(подраздел1(список1, список2)), ...))))

****Или Вы решаете проблему распознания неизвестной структуры СЛОВАРЯ, то есть не знаете как разграничены его разделы, как разграничены слова в разделах? Тогда придется проверять различные гипотезы ( примеры таковых выше даны).

[vv40in]

ewert писал(а):

vv40in в сообщении #186081 писал(а):

Надо найти в данных любое слово из словаря.

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

Надо найти в данных любое слово, содержащееся в словаре.

ewert писал(а):

vv40in в сообщении #186081 писал(а):

А что - это важно? По-моему для поиска это не существенно.

Существенно. Существуют ли символы-разделители?
Или Вам надо просто какой-то архиватор сочинить?

Нет разделителей. Но и это не существенно для поиска.
И что в итоге надо - тоже не существенно. Но надо алгоритм поиска.

Так что : trie?

[ewert]

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

[Архипов]

vv40in в сообщении #186097 писал(а):

Нет разделителей. Но и это не существенно для поиска.
И что в итоге надо - тоже не существенно. Но надо алгоритм поиска.

Есть простой алгоритм поиска заданного слова. Например: найти в словаре слово "капут" . Запускается цикл поиска первого символа "к" в словаре, затем цикл проверки следующих символов "а, п, у, т". Если эти 4 символа не совпадают с заданной последовательностью - ищем следующий символ "к" и опять 4 символа проверяем.
Примечание: таким способом мы ищем заданную комбинацию символов в длинной строке, но не слово, так как для Вас разделители не существенны.

[vv40in]

ewert писал(а):

Надо найти любое конкретное слово из словаря -- или хоть одно слово, содержащееся в словаре? найти только первое вхождение -- или все?

найти любое слово, которое встретится в данных, и продолжить поиск.

ewert писал(а):

и могут ли слова накладываться (например: "аббаббабба" -- это одно слово "абба", или два, или даже три?)

1. префиксы не могут быть отдельными словами (пол и полковник - нельзя).
2. да. слова могут накладываться. даже могут содержаться друг в друге. но это влияет только на то, откуда поиск будет продолжен после события обнаружения - со следующего байта. но и ЭТО по существу не влияет на поиск! - разве что только на оптимизацию.

и воще ... кто тут вопросы задает: Вы или я ?

Добавлено спустя 9 минут 38 секунд:

Архипов писал(а):

Есть простой алгоритм поиска заданного слова. Например: найти в словаре слово "капут" . Запускается цикл поиска первого символа "к" в словаре, затем цикл проверки следующих символов "а, п, у, т". Если эти 4 символа не совпадают с заданной последовательностью - ищем следующий символ "к" и опять 4 символа проверяем.
Примечание: таким способом мы ищем заданную комбинацию символов в длинной строке, но не слово, так как для Вас разделители не существенны.

1)циклы ни в коем случае нельзя использовать! у нас в словаре 50000 слов!!!
это сеть, а не гуи для пользователя-секретарши . даже простые B-деревья быстрее. таблицы индексов - лучше. но и это не лучший вариант, как говорит начальник. а какой лучший - не говорит
2) оцените быстродействие предложенного Вами варианта. она никак не log(n), а гораздо хуже. а надо log(n) или лучше, если возможно!

[Архипов]

Архипов в сообщении #186106 писал(а):

1)циклы ни в коем случае нельзя использовать! у нас в словаре 50000 слов!!!

Так циклы не фиксированные, а с условным выходом из них в случае первой же неудачи. Нашли первую букву "к", если следующая не "а", то ищем следующую "к".
Вы утверждаете, что в словаре 50000 слов. Но ведь слова должны иметь признаки начала и конца. Если иначе, то как Вы посчитали количество слов?

[vv40in]

Архипов писал(а):

Архипов в сообщении #186106 писал(а):

1)циклы ни в коем случае нельзя использовать! у нас в словаре 50000 слов!!!

Так циклы не фиксированные, а с условным выходом из них в случае первой же неудачи. Нашли первую букву "к", если следующая не "а", то ищем следующую "к".
Вы утверждаете, что в словаре 50000 слов. Но ведь слова должны иметь признаки начала и конца. Если иначе, то как Вы посчитали количество слов?

слова не имеют ни начала ни конца, т.к. они могут содержать любой набор байтов, в т.ч. нули и др.непечатные и пахабные символы . прочитайте вопрос. я разве где-то упоминал подсчет слов? О чем речь? Вы перепутали тему?
и никакий циклов! Вы что, хотите в цикле перебрать все 50000 слов?
ведь в данных (с самого первого байта) может быть любое слово словаря.

[Архипов]

vv40in в сообщении #186128 писал(а):

Вы что, хотите в цикле перебрать все 50000 слов?
ведь в данных (с самого первого байта) может быть любое слово словаря.

1) Проблема теоретическая или практическая?
2) Если искомое слово "караул" единственно (уникально) в словаре, то поиск продолжится до того места в словаре, где искомое слово находится (на этом цикл обрывается).
3) Если искомое слово "караул" не уникально (повторяется), то придется перебрать все 50000 слов, чтобы найти все слова "караул" в этом файле.

[Cave]

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

Поэтому предлагаю использовать именно алгоритм поиска подстроки в строке, который делает предобработку за время $O(m)$ и использует столько же памяти, а затем за $O(n)$ с $O(1)$ памяти решает задачу, $n$ - длина текста, $m$ - длина слова в словаре. Под эти критерии подходит, например, алгоритм Кнута-Морриса-Пратта.

[vv40in]

Архипов писал(а):

1) Проблема теоретическая или практическая?

как отразится на алгоритме поиска если я отвечу теоретическая? или практическая?

Архипов писал(а):

2) Если искомое слово "караул" единственно (уникально) в словаре, то поиск продолжится до того места в словаре, где искомое слово находится (на этом цикл обрывается).

но в словаре 50000 и перед "караул" м.стоять 49999.

Архипов писал(а):

3) Если искомое слово "караул" не уникально (повторяется), то придется перебрать все 50000 слов, чтобы найти все слова "караул" в этом файле.

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

ну, если свежих мыслей нет, возьмусь пользовать TST-деревья.

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

Добавлено спустя 16 минут 35 секунд:

Cave писал(а):

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

Поэтому предлагаю использовать именно алгоритм поиска подстроки в строке, который делает предобработку за время $O(m)$ и использует столько же памяти, а затем за $O(n)$ с $O(1)$ памяти решает задачу, $n$ - длина текста, $m$ - длина слова в словаре. Под эти критерии подходит, например, алгоритм Кнута-Морриса-Пратта.

Вы тоже предлагаете в цикл по словарю с просмотром внутри него всего массива данных? или я не так понял?

TST обеспечит O(M*log(N)). или нет, лучше чем: O(M*log(256)). (256 - длина алфавита). или лучше чем: O(M/2*log(0x10000)) 0x10000-если производить выборку и сранение словами.
я как раз ищу идеи получше. начальник сказал, что они есть. или мы не поняли др.друга (т.е. он меня не захотел услышать - я ведь не красноречив ).

[Cave]

vv40in
Увы, да, и получится высокая сложность - $O(KN)$, где $K$ - число слов в словаре.
Однако заметим, что если слова в словаре имеют вид $a, aa, aaa, \ldots, aa\ldots a$ - в последнем слове $K$ букв $a$, а текст состоит из $N$ букв $a$, $N>K$, то число вхождений слов словаря в текст суммарно равно $N + (N - 1) + \ldots + (N - K) = NK - C_{k+1}^2$, что с ростом $N$ даёт такую нижнюю оценку (ведь каждое вхождение слова в текст будет отмечено или хотя бы выведено - в этом задача состоит).