Перебор текста по словарю

← →
_mik © (2006-07-14 22:18) [0]

Сдравствуйте!

Как можно организовать быстрый перебор теста по словарю!

Причем словарь имеет довольно большой размер ~35000 слов и словосочетаний!, причем синтаксис словаря такой:
[$][*][слово][*]=[чему то]
где
$ - учитывать ли индекс;
* - любое кол-во символов;

← →
Leonid Troyanovsky © (2006-07-14 22:34) [1]

> _mik © (14.07.06 22:18)
> Сдравствуйте!

И тебе тогож.

> Как можно организовать быстрый перебор теста по словарю!

MSSQL.

> [$][*][слово][*]=[чему то]

Плиз, подробней, про [чему то].

--
Regards, LVT.

← →
Gero © (2006-07-15 00:14) [2]

Последовательным перебором и проверкой каждой строки на соответствие шаблону.

← →
Servelat © (2006-07-15 01:40) [3]

> Плиз, подробней, про [чему то].

подозреваю, что что-то - это перевод слова, если словарь иностранного языка =).

> перебор теста

какого такого теста?

← →
Leonid Troyanovsky © (2006-07-15 01:45) [4]

> rvelat © (15.07.06 01:40) [3]

> перебор теста

> какого такого теста?

Ну, хоть какого-нибудь.

--
Regards, LVT.

← →
Pavia © (2006-07-15 15:32) [5]

Я бы помог автору если понял, что нужно.

> перебор теста по словарю!

Что сие значит? Найти слово или слово сочитание в словоре?
Ну так это просто. B+ деревья или поиск по хэш.

← →
Ketmar © (2006-07-15 16:33) [6]

RBTrees. AVLTrees. и ты ды, и ты пы... подробности, блин, подробности!

← →
_mik © (2006-07-16 21:32) [7]

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

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

← →
_mik © (2006-07-16 21:35) [8]

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

Тупой перебор на Pentium 2.4HT теста ~500 символов занимает 10 сек при полной загрузки процессора, что для меня не приемлемо!

п.с. если когота заинтересовал компонент для работы с голосовыми движками (spichapi 4.0) могу выложить!

← →
Virgo_Style © (2006-07-16 21:55) [9]

БД, "грубая" выборка с помощью LIKE, затем проверка?

← →
_mik © (2006-07-16 22:29) [10]

Нет я не использую БД, в дянный момент я использую тестовый файл, который грузится в TStringList после чего я беру первое слово из теста и ищу
бинарным поискомв словаре подходящее слово, а затем меняю!

Даже со словарем в 150 тыс слов (без обобщающих символов, кроме
"$" - учитывать ли регистр или нет)
к списку во время поиска программа обращается от силы 30~40 раз!

Я бы хотел реализовать обобшающие символы:
например: "*" хотябы в начале и конце слова,
а также поддержку словосочетаний для обработки ОМОГРАФОВ!

← →
_mik © (2006-07-16 22:34) [11]

Уточню формат ловаря

[$][*]слово[*]=замена

например:
$Москва=мос>ква
или

2012-й г=две тысячи двена<дцатый год
$*—ХIX=- 19

т.е. если в тексте встретится например: "Москва" то она должна поменятся на "мос>ква"

← →
Virgo_Style © (2006-07-16 22:47) [12]

Бинарный поиск занимает 10 секунд для ~500 символов (грубо - 100 слов)? Хм...

Я бы пользовался не StringList, а массивом записей (и вынес бы флаги в отдельные поля). А можно и БД попробовать...

← →
_mik © (2006-07-16 23:22) [13]

Нет бинарный поиск, я начал использовать не давно!

Грубый перебор текста на наличие вхождений всех записей словаря начинающихся например с символа "*", да еще и наличие словосочетаний в словаре сильно замедляет процесс замены!

По этому в данный момент, я отказался от словосочетаний и обобщающих символов и испоьзую бинарный поиск!

← →
Ketmar © (2006-07-17 03:43) [14]

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

← →
_mik © (2006-07-17 10:10) [15]

- А каким образом можно написать свои регулярные выражения без конечных автоматов?

- Да так, чтобы не потерять при этом скорость обработки?

← →
Ketmar © (2006-07-17 10:19) [16]

>_mik © (17.07.06 10:10) [15]
а вот сесть -- и написать. досовые маски -- тоже регэкспы. Вы и для них будете автомат городить?
фильтры -- тоже в какой-то мере регэкспы. можно написать без автоматов.
и так дале...

← →
_mik © (2006-07-17 12:08) [17]

Спасибо.
А где мне взять подробный материал?

← →
Ketmar © (2006-07-17 12:34) [18]

в интернете? %-)

← →
atruhin © (2006-07-17 13:20) [19]

По условия задачи не нужно ни каких регулярных выражений (это не очень быстро).
Во первых:
ОБЯЗАТЕЛЬНО убери из строк равно и сделай двумерный массив + модификаторы. Сократится область поиска.
Далее: словарь сделать отсортированным, сделать хэш по первым символам, далее бинарный поиск в оставшемся фрагменте.
Далее двигашся по текстовому потоку выбираеш слово ищеш в словаре, если найдено пытаешся удлиннить (т.е. словосочитание), если не найдено поиск по кажддой букве.
Думаю будет работать на несколько порядков быстрее. На самом деле подходящих алгоритмов много.
PS Не понимаю одного в задаче, на входе слово содружество в словаре его нет , нашли дружество запомнили, а куда девать со

← →
_mik © (2006-07-17 16:59) [20]

Спасибо за дельный совет!

В настоящее время я деляю так:

1 выбираю кусок текста и разбиваю его на составные части путем добавления после каждого слова символов #10#13 а затем помещаю все в
StringList

2 обращаюсь через метод StringList.items к отдельным словам и произвожу поиск их по словарю, а затем меняю!

примерно так:

str := TStringList.Create();
_GetTextBlock (REEdit.Text, SpeechPosition, str);
// вставляем теги
_TextAnalise (str);
// отслеживание позиции чтения
_TextHig (0,SpeechPosition, clGreen);
// замена по словарю
replaseOnDic (str);
TTSSpeech.Speech(str.Text);

где

procedure replaseOnDic (var Data: TStringList);
var i, psn: Integer;
str1, str2: String;
begin
for i:=0 to Data.Count-1 do
begin
str1 := Data.Strings[i];

if str1[1] in separators then continue;
{separators - множество разделителей слов set of char = [",", ".", ":"]}

// проверка на регистрозависимость
psn:=FindItem ("$"+str1);
if psn>=0 then
begin
{получаем слово перед знаком "="}
str1:=GetDest(SEDicEditor.Lines[psn]);

Data.Strings[i]:=str1;
continue;
end;

// замена текста
str1:=AnsiLowerCase (str1);
psn:=FindItem (str1);
if psn>=0 then
begin
{получаем слово после знака "="}
str1:=self.GetDest(SEDicEditor.Lines[psn]);
{SEDicEditor - TStringList со словарем}
Data.Strings[i]:=str1;
end;

end;
end;

← →
Stanislav © (2006-07-17 17:14) [21]

Для начала словарь данных нужно отсортировать и вести поиск не по всем записям, а по сортированным.

Лучше всего использовать БД. хотябы организованную на MS ACCESS т.к. алгоритмы быстрого поиска там уже реализованы.

← →
atruhin © (2006-07-17 17:53) [22]

> [21] Stanislav © (17.07.06 17:14)

Незачем использовать БД где не попадя. Словарь фиксированный, маленький. Менее 1 мб, поиск в памяти будет эффективнее.

> [20] _mik © (17.07.06 16:59)

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

> PS Не понимаю одного в задаче, на входе слово содружество
> в словаре его нет , нашли дружество запомнили, а куда девать
> со

← →
_mik © (2006-07-17 18:05) [23]

Вообще я привел то, что работает хорошо!
Я уже писал, что я произовожу бинарный поиск по словарю (это значит что словарь заранее отсортирован)

Вариант с базой данных мне не подходит, т.к. я планирую использовать программу на компютерах с win95 и выше! (не охото утяжилять дистрибутив драйверами)
Плюс к тому, я пытаюсь обеспечить совместимость по словарями ГОВОРИЛКИ!

В Данный момент я не могу решить проблему с быстрым поиском слов и словосочетаний по маске, т.е. с обобщающими символами!

Подчеркиваю именно быстрого!!
СПАСИБО ЗА СОВЕТЫ

← →
Ketmar © (2006-07-17 20:45) [24]

насчёт регулярных выражений. проверил только что свой движок (далеко не самый шустрый, кстати). на файле объёмом 400 кил отрабатывает практически мгновенно. машина -- pIII/600. просто dos-like wildcards ещё шустрее.

← →
_mik © (2006-07-17 20:49) [25]

А не мог бы ты привести исходники!
Или хотябы адрес сайта с которого ты взял информацию!
Спасибо!

← →
_mik © (2006-07-17 20:50) [26]

Лучше приведи (или пошли напочту если не жалко)информацию по написанию!
Это очень интересно!
СПАСИБО!

← →
Ketmar © (2006-07-17 21:39) [27]

>_mik © (17.07.06 20:50) [26]
к сожалению, переходник "мозг-USB" ещё не придумали. а писать статью мне лениво. %-)

← →
_mik © (2006-07-17 21:51) [28]

Может хотябы исходиники скинеш?
viri@yandex.ru

может, хотя бы в анкету глянешь? %-)

Спасибо!

не вопрос. если поймёшь, как и почему оно работает -- поделись знанием. я не понимаю. %-)

Если БД на ACCESS драйвера не нужны.

Тупой перебор на Pentium 2.4HT теста ~500 символов занимает 10 сек при полной загрузки процессора, что для меня не приемлемо!

Это очень медлено. Ты дольше провозишься с оптимизацией поиска, и всеравно такой скорости как у БД не добьешься.
Хотя есть примеры в книгах быстрой сортировки, это сортировка путем половинчатого деления.

> Ты дольше провозишься с оптимизацией поиска, и всеравно
> такой скорости как у БД не добьешься.

Почему ты так решил? В БД что поиск какой то особенный секретный. Все алгоритмы известны. Реализуются максимем за 1 день. Можно найти готовые реализации. А алгоритм заточенный под конкретную задачу будет быстрее.
Автору:
Не нужны в данном случае регулярные выражения, да и как ты их хочешь прикрутить?

>Stanislav © (18.07.06 09:45) [32]
> Если БД на ACCESS драйвера не нужны.
да??? ого. Дед Мороз приносит?

>atruhin © (18.07.06 18:20) [33]
нафиг не нужны. просто разговор о них зашёл. %-)

Автору.
Ты так и не ответил на вопрос:
> PS Не понимаю одного в задаче, на входе слово содружество
> в словаре его нет , нашли дружество запомнили, а куда девать
> со

От этого сильно зависит алгоритм и все советы. Например:
Есть предложение:
"абвгд ежзи клм"
есть слова в словаре:
*бвгд е*
*гд ежзи ел*
Что должен найти алгоритм, более длинную или с которой раньше начинается?
И что делать с первыми (пропущеными) буквами?

Ketmar © (18.07.06 20:41) [34]
Ага, Только не дед могроз, а стандартная поставка Windows.
atruhin © (18.07.06 18:20) [33]
Может и за день, но мы тут 5 дней уже разговариваем.

Поиск слов и словосечетаний в словаре я уже решил!
это можно сделать:

- либо бинарным поиском, что реализуется довольно просто
а скорость выполнения данной операции составляет O(log n)
- либо при помощи хэш таблиц при этом скорость будет O(1) что еще быстрее

вся загвоздка состоит в замене в тексте с использованием "*",
Например:

есть текст : "http:\\www.randex.ru"
и есть определение в словаре: "*www*=вэ вэ вэ"

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

"http:\\вэ вэ вэ.randex.ru"

Причем таких записей в словаре как "*www*=вэ вэ вэ" может быть несколько сотен!

А. Теперь я врубился. Фактически, в словаре у тебя шаблоны, и рассматривая строку ты прилагаешь к ней все шаблоны (оптимизируя выбор), делая замену какая пойдет. Так?
Ты лучше скажи полностью постановку. Что * - любое число символов, я понял, а что такое $? И что еще есть?

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

фактически шаблон выглядит так
"$*слово*"
причем обобщающих символов может и не быть
например:
"*слово"
или
"$слово*"
"$слово"
"слово"
"$*слово"
ну и тп.

где символ $ означает сравнение с учетом регистра,
да и еще "*" могут распологатся только в начале, либо в конце слова!

Перебор текста по словарю Найти похожие ветки