VPF::Алгоритм формирования списка верных слов

Insert

Дата 12.4.2007, 22:58 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 208
Регистрация: 13.4.2006

Репутация: 1
Всего: 1

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

--------------------

пьяный русский кодер практически непобедим

Sunvas

Дата 13.4.2007, 12:00 (ссылка)

(нет голосов)

Загрузка ...

Соль и сахар

Профиль
Группа: Участник
Сообщений: 3388
Регистрация: 12.3.2006
Где: Тосно

Репутация: 28
Всего: 89

Цитата(Insert @ 12.4.2007, 22:58

)

вот сделал проверку орфографии

Как же ты ее сделал если у тебя нет списка правильных слов?

--------------------

Воспитывая детей по своему образу и подобию, родители почему-то надеются, что они будут лучше их.

Insert

Дата 13.4.2007, 12:24 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 208
Регистрация: 13.4.2006

Репутация: 1
Всего: 1

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

--------------------

пьяный русский кодер практически непобедим

MaXL

Дата 14.4.2007, 01:58 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 380
Регистрация: 24.10.2005
Где: Владивосток

Репутация: нет
Всего: 2

Insert, привет. Я как раз тоже сейчас этим занимаюсь, нашёл что такое можно реализовать с помощью расстояния Левеннштейна.
Вот ссылка по теме:
http://itman.narod.ru/source/source.html

Это сообщение отредактировал(а) MaXL - 14.4.2007, 01:58

--------------------

MaXL

Insert

Дата 14.4.2007, 08:55 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 208
Регистрация: 13.4.2006

Репутация: 1
Всего: 1

MaXL, так нада посмотреть, если будут какие то результаты у меня я тут отпишусь.

--------------------

пьяный русский кодер практически непобедим

Sardar

Дата 14.4.2007, 11:56 (ссылка)

(нет голосов)

Загрузка ...

Бегун

Профиль
Группа: Модератор
Сообщений: 6986
Регистрация: 19.4.2002
Где: Нидерланды, Groni ngen

Репутация: 2
Всего: 317

Собери в словарь в trie, затем ищи вычисляя расстояние Левенштейна. В идеале разным операциям можно дать разные веса, нпаример ошибкам синхронизации можно дать вес выше чем остальным. Сортируешь список по расстоянию, берёшь первые 5.

--------------------

Опыт - сын ошибок трудных © А. С. Пушкин
Процесс написания своего велосипеда повышает профессиональный уровень программиста. © Opik
Оценить мои качества можно тут.

Святогор

Дата 14.4.2007, 12:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 105
Регистрация: 9.8.2006

Репутация: нет
Всего: нет

MaXL,
Ну а вообще есть ещё инфа по-поводу проверки орфографии ? Мне для англ. языка нужно.

MaXL

Дата 14.4.2007, 15:11 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 380
Регистрация: 24.10.2005
Где: Владивосток

Репутация: нет
Всего: 2

Святогор, помоему реализация этого алгоритма не операется на конкретные языки(русский, китайский, немецкий, английский...). Просто какие ты ему входные данные подкинешь с таким он и будет работать. Я ещё пока с этим алгоритмом не занимался, так в данный момент перекинулся на кое - что другое, но вскоре к этому опять вернусь.
Вот ещё ссылка: www.levenshtein.net/.
P.S. да и как мне кажется по этому вопросу можно обратиться в раздел "Алгоритмы" этого форума, уверен что помогут.

--------------------

MaXL

Insert

Дата 16.4.2007, 23:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 208
Регистрация: 13.4.2006

Репутация: 1
Всего: 1

Так так есть кое какие результаты, вот нашел две реализации неточного поиска, один вычисляет расстояние Левинштейна, другой возвращает в % похожесть одной строки на другую(взят с vingard)

Расстояние Левинштейна:

Код



var
  const cuthalf = 100;
  buf: array [0..199] of integer;

function min3(a, b, c: integer): integer;
begin
  Result := a;
  if b < Result then Result := b;
  if c < Result then Result := c;
end;

function Levenstain(s, t: string): integer;
var i, j, m, n: integer;
    cost: integer;
    flip: boolean;
begin
  s := copy(s, 1, cuthalf - 1);
  t := copy(t, 1, cuthalf - 1);
  m := length(s);
  n := length(t);
  if m = 0 then Result := n
  else if n = 0 then Result := m
  else begin
    flip := false;
    for i := 0 to n do buf[i] := i;
    for i := 1 to m do begin
      if flip then buf[0] := i
      else buf[cuthalf] := i;
      for j := 1 to n do begin
        if s[i] = t[j] then cost := 0
        else cost := 1;
        if flip then
          buf[j] := min3((buf[cuthalf + j] + 1),
                         (buf[j - 1] + 1),
                         (buf[cuthalf + j - 1] + cost))
        else
          buf[cuthalf + j] := min3((buf[j] + 1),
                                   (buf[cuthalf + j - 1] + 1),
                                   (buf[j - 1] + cost));
      end;
      flip := not flip;
    end;
    if flip then Result := buf[cuthalf + n]
    else Result := buf[n];
  end;

end;

Вот который возвращает похожесть в процентах:

Код




function testpercent(s1,s2: string): double;
var i,j,max: longint;
chto_ishem, v_chem,test: string;
begin
max:=0;
   if Length(s1)>Length(s2) then
   begin
   chto_ishem:=s2;
   v_chem:=s1;
   end else
   begin
    chto_ishem:=s1;
   v_chem:=s2;
   end;
   for i:=1 to Length(chto_ishem) do
   for j:=Length(chto_ishem)+1-i downto i do
    begin
   test:=copy( chto_ishem,i,j);
   if (Pos(
   test
   ,v_chem)>0) then
   if (max<Length(test))
   then
   max:= Length(test);
   end;
   Result:=max*100/Length(v_chem);
end;

Так вот
Sardar, писал что неплохо было бы сформировать из словаря префиксное дерево, можно об этом поподробнее... кстати в моем случае все содержимое словаря недоступно, есть только функция на проверку наличия слова в словаре, чувствую этого будет маловато, может есть ещё варианты куда двигаться?

--------------------

пьяный русский кодер практически непобедим

Insert

Дата 17.4.2007, 09:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 208
Регистрация: 13.4.2006

Репутация: 1
Всего: 1

В моем словаре 180 000 оснований слов, если их перебирать и для каждого вычислять расстояние Левинштейна, то это будет очень долго, есть какие нить варианты ускорить поиск. Как я понял, если искать по префиксному дереву, то будет намного быстрее, но как весь словарь забить в него?

--------------------

пьяный русский кодер практически непобедим

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Общие вопросы \| Следующая тема »