Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2006.09.03;
Скачать: CL | DM;

Вниз

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

 
_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*=вэ вэ вэ" может быть несколько сотен!


 
Romkin ©   (2006-07-19 18:37) [38]

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


 
Romkin ©   (2006-07-19 18:40) [39]

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


 
_mik ©   (2006-07-19 19:09) [40]

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

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


 
Pavia ©   (2006-07-19 19:55) [41]

Нет проблем ты когда строку разбираешь на слова. Ты затем будешь перебирать все варианты слова, которые можешь составить из данного слова путем удоления нескольких символов с начала или с конца. 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] Так * - это начало слова? Или текста?
почему нельзя вместо * ставить пробел?
Если убрать *, то у тебя словарь распадается на три, префиксов, суффиксов и подстановок слов?


 
_mik ©   (2006-07-19 20:44) [43]

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


 
_mik ©   (2006-07-19 20:45) [44]


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


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


 
Ketmar ©   (2006-07-19 22:12) [45]

>_mik ©   (19.07.06 19:09) [40]
простейший фильтр.


 
Pavia ©   (2006-07-19 23:38) [46]

А что с * звездочками? А я про что говорил.
Вот перебор.
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.
Медленный класс. Я бы просто использовалбы строку или строки.


 
Romkin ©   (2006-07-20 11:47) [47]

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


 
_mik ©   (2006-07-20 12:12) [48]

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


 
_mik ©   (2006-07-20 12:16) [49]

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

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

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


 
Romkin ©   (2006-07-20 12:26) [50]

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


 
_mik ©   (2006-07-20 14:22) [51]

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

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

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

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


 
atruhin ©   (2006-07-20 16:08) [52]

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


 
_mik ©   (2006-07-20 18:09) [53]

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



Страницы: 1 2 вся ветка

Текущий архив: 2006.09.03;
Скачать: CL | DM;

Наверх




Память: 0.63 MB
Время: 0.053 c
6-1144955552
qazwsx
2006-04-13 23:12
2006.09.03
base64_encode(pack("H*", sha1(utf8_encode($_GET[ pwd ])))))


15-1155210605
Opilki_Inside
2006-08-10 15:50
2006.09.03
Статическая переменная


15-1155410696
Virgo_Style
2006-08-12 23:24
2006.09.03
Всех причастных к ВВС РФ -


15-1155309115
Rouse_
2006-08-11 19:11
2006.09.03
Небольшой анонсик одной полезной утилиты, PEDump Shell Extension


15-1155211149
Desdechado
2006-08-10 15:59
2006.09.03
Не пятница.... но разминка для мозгов