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

← →
_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

← →
Ketmar © (2006-07-17 23:35) [29]

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

← →
_mik © (2006-07-18 01:10) [30]

Спасибо!

← →
Ketmar © (2006-07-18 01:53) [31]

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

← →
Stanislav © (2006-07-18 09:45) [32]

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

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

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

← →
atruhin © (2006-07-18 18:20) [33]

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

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

← →
Ketmar © (2006-07-18 20:41) [34]

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

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

← →
atruhin © (2006-07-18 22:49) [35]

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

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

← →
Stanislav © (2006-07-19 10:45) [36]

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

← →
_mik © (2006-07-19 18:21) [37]

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

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

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

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

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

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

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

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

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

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

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

Нет проблем ты когда строку разбираешь на слова. Ты затем будешь перебирать все варианты слова, которые можешь составить из данного слова путем удоления нескольких символов с начала или с конца. N*(N-1)/2 вариантов.
И еще совет откажись от класса TStringList.

← →
Romkin_ (2006-07-19 20:16) [42]

Pavia © (19.07.06 19:55) [41] Обычно, когда говорят "откажись", указывают альтернативу ;)
_mik © (19.07.06 19:09) [40] Так * - это начало слова? Или текста?
почему нельзя вместо * ставить пробел?
Если убрать *, то у тебя словарь распадается на три, префиксов, суффиксов и подстановок слов?

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

> Нет проблем ты когда строку разбираешь на слова. Ты затем
> будешь перебирать все варианты слова, которые можешь составить
> из данного слова путем удоления нескольких символов с начала
> или с конца. N*(N-1)/2 вариантов.
> И еще совет откажись от класса TStringList.

а как же быть когда в словаре есть слово с двумя "*" в начале и в конце?

А что с * звездочками? А я про что говорил.
Вот перебор.
function strings(s:string):string;
var i,j:Integer;
ss,ss1,ss2,ss3:string;
begin
result:="";
For i:=Length(s) downto 1 do
For j:=1 to Length(s)-i+1 do
begin
ss:=copy(s,j,i);
ss2:=Find(ss);
if ss2<>"" then
ss2:=Find("*"+ss);
if ss2<>"" then
ss2:=Find(ss+"*");
if ss2<>"" then
ss2:=Find("*"+ss+"*");
if ss2<>"" then
ss2:=Find("$*"+ss);
if ss2<>"" then
ss2:=Find("$"+ss+"*");
if ss2<>"" then
ss2:=Find("$*"+ss+"*");
if ss2<>"" then
begin
if copy(s,1,j-1)="" then ss1:=""
else ss1:=strings(copy(s,1,j-1));
if copy(s,j+i,Length(s)-j-i+1)="" then ss2:=""
else ss3:=strings(copy(s,j+i,Length(s)-j-i+1));
result:=ss1+ ss2+ss3;
exit;
end;
end;
end;
Find(ss)- поиск строки, я бы сделал через хэш таблицы.
И еще совет откажись от класса TStringList.
Медленный класс. Я бы просто использовалбы строку или строки.

_mik © (19.07.06 20:44) [43] Я правильно понял - если звездочки, то это часть слова, а если нет - слово целиком на замену?
То есть, звездочка означает ограничение буквами, ее отсутствие - ограничение разделителями (пробел, запятая и тд)?
Тогда ведь можно обобщить, заменить все разделители слов на пробел, а в словаре избавится от звездочек, присоединив к словам без звездочки пробелы. То есть "АБ" переходит в " АБ ", а "*АБ*" переходит в "АБ"?

Ты не совсем правильно понял >Romkin!
да "*АБ*" означает часть слова содержащего "АБ", причем "АБ" должно быть ограничено буквами, а если звездочек не то разделителями!
Но удалять разделители я не могу, это приведет к потери части смысла текста!
(Яже пишу программу озвучивания текста)

>Pavia Спасибо!
Но насколько японял, твой алгоритм онтносится примерно к O(n^2) при больших значениях!
А это я думаю врятли допустимо!
Поскольку в словаре слов со звеждочкой может быть порядка ~700-1000!
Это приведет к сильному падению быстродействия!

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

Хотя я попробую, наверное вечером отпишусь!

_mik © (20.07.06 12:12) [48] А никто не заставляет тебя удалять их совсем. Только на вход словаря подавай с заменой. А после замены - присоединяй. Или знаки препинания тоже преобразуются?
Вообще говоря, какой объем словаря? Можешь согласится с увеличением этого объема раз в 5-10? Если использовать дерево, то можно достичь примерно O(NlogM) по моей первой прикидке, где N - число символов текста, M - число слов в словаре... (или символов? - с утра плохо думается) Или не так, но блиизко. Но за счет объема

Спасибо за советы!
Но для деревьев я пока еще мал!
Я только начинаю вникать в основные концепции!
и некоторы вещи мне сложновато понять!

я опробовал процедуру Pavia и она дола приемлемое быстродейстиве!

PS если когото интересует компонент для подключения TTS движка на основе SAPI 4 то могу скинуть на почту!

PPS о всех результатах дольнейшей работы буду сообщать сдесь!

Вообще эта задача описана: Бакнел. "Фундаментальные алгоритмы и структуры данных в Delphi" последняя глава, сравнение текстовых файлов.
PS. Можно найти в сети.

я этоу книжку уже нашел!
сейчас дочитываю!
СПАСИБО!

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