Вход | Регистрация


Информационные технологии ::

Метки:

Нужна функция для стемминга на PHP

Я
   Волшебник
 
Модератор
29.11.05 - 20:16
Есть готовая функция на С, нужно их перевести на язык PHP или подключить к PHP. Кто поможет?

Функция предназначена для обработки слов на русском языке. С помощью нее можно получить выделить основу слова, отбросив окончания. Эта функция будет использована для поиска по форуму. Например, вы ищете "иерархический", а в результате находятся "иерархический", "иерархического" и т.д.

Практика показала, что использование штатных возможностей MySQL - FULLTEXT-индек и IN BOOLEAN MODE со звездочкой страшно тормозит. Звездочка как раз использовалась для того, чтобы искать слово без окончания, т.е. создавалась видимость поиска слова по всем его словоформам.

Думаю, с помощью этой функции можно не просто отбросить окончание, а отбросить его более точно. Просто нужно ее перевести на язык PHP для встраивания в движок форума. Кто поможет?
 
 
   Трезвый взгляд
 
1 - 29.11.05 - 20:37
а если отбрасывать окончания, содержащиеся в списке окончаний ("ая" "яя" "ый" "ий" и т.д.)
   КонецЦикла
 
2 - 29.11.05 - 20:37
2(0) Выкупи технологию у Яндекса
   Camino
 
Модератор
3 - 29.11.05 - 20:44
(0) А ты уже в аське?
   Asmody
 
4 - 29.11.05 - 20:45
если я чего-то где-то понимаю, то у php есть такие extentions... в win-версии они реализованы как dll. возмжно сюда покопать?
   ИвановИван
 
5 - 29.11.05 - 20:55
эээ я бы помог, но немогу ((
   Волшебник
 
Модератор
6 - 29.11.05 - 21:17
(1) иногда отбрасывается часть слова.
(2) денег жалко
(3) да
(4) win-версии не нужны. Форум крутится на FreeBSD. Что за extensions? можно ссылки? из тех, что я нашел в pecl, ничего не подходит для русского языка.
(5) жаль
   smaharbA
 
7 - 30.11.05 - 01:05
regexp
   Волшебник
 
Модератор
8 - 30.11.05 - 07:23
(7) Наивный...
   smaharbA
 
9 - 30.11.05 - 07:24
(8) Ага
   Волшебник
 
Модератор
10 - 30.11.05 - 07:27
Описание метода и сама функция находится здесь:
http://linguist.nm.ru/stemka/stemka.html

Приведение к нормальной форме без всяких словарей. Используется только словарь окончаний и уже рассчитанные коэффициенты вероятностей.
 
  AdBlock убивает бесплатный контент
   smaharbA
 
11 - 30.11.05 - 07:30
   Волшебник
 
Модератор
12 - 30.11.05 - 07:42
(11) Уже ближе к теме.
   smaharbA
 
13 - 30.11.05 - 07:43
   smaharbA
 
14 - 30.11.05 - 07:50
Вот вроде почти готовое
http://search.cpan.org/~algdr/Lingua-Stem-Ru-0.01/Ru.pm#___top
   Asmody
 
15 - 30.11.05 - 08:47
(13) про [кракозябль] мне там понравилось :)
   Волшебник
 
Модератор
16 - 30.11.05 - 09:21
(14) Очень интересно. Думаю, если подключить расширение Perl для PHP, то можно будет вызывать Perl-код из PHP-скрипта.

Расширение Perl позволяет вызывать Perl-скрипты, использовать объекты Perl и использовать другие функциональные возможности Perl-а прямо из кода PHP. По умолчанию оно не включено в PHP5. Это новое расширение можно найти в репозитории PECL.

http://pecl.php.net/package/perl
   Deon
 
17 - 30.11.05 - 09:39
Переделывать ещё нужно или уже можно забить?
   Волшебник
 
Модератор
18 - 30.11.05 - 09:40
(17) Пока не знаю. Функции-то разные. Я хочу их сравнить по качеству работы и выбрать одну. Если удастся подключить perl-функцию и она будет вполне сносно работать, то на ней и остановимся.
   Волшебник
 
Модератор
19 - 30.11.05 - 09:48
(17) Если есть возможность, то помоги перевести. Та функция на С очень простая, не превышает 100 строчек. Основную ценность представляют уже рассчитанные вероятности. И не требуется наличие словаря. Т.е. функция уже обученная, следовательно работать будет быстро.

Скорость работы функции очень важна. Поскольку она будет срабатывать при каждом добавлении сообщения почти над каждым словом. Если будет вызываться perl, то будут лишние накладные расходы по созданию процессов, загрузке модуля Perl и т.д.
Поэтому самым лучшим вариантом будет переписать ту функцию на PHP.
   Deon
 
20 - 30.11.05 - 10:13
(19) Там чё-то много, какую именно функцию перевести-то нужно?
   Волшебник
 
Модератор
21 - 30.11.05 - 10:22
(20) Скачиваешь архив http://linguist.nm.ru/stemka/stemka.tar.gz
В нем есть каталоги example, include, library.

Нужно перевести на PHP следующие скрипты:

1. stemmers.h + stemmers.c - основной скрипт. Смысловая часть занимает около 50 строчек.

2. checkrus.cpp - клиентская часть, пример вызова функции

Файлы fuzzyrus.c + fuzzyrus.inc программного кода не содержат, а содержат таблицу вероятностей для русского языка в 16-ричных кодах.
   Волшебник
 
Модератор
22 - 30.11.05 - 18:32
Кстати, Stemming (или по-русски, "лемматизация", т.е. выделение неизменяемой основы слова) находится в списке Full-Text Search TODO http://dev.mysql.com/doc/refman/5.0/en/fulltext-todo.html

Поэтому, если у нас будет такая функция, то наш форум станет первым PHP-форумом, использующим штатные возможности FULLTEXT-поиска MySQL на большой базе сообщений с учетом словоформ и без применения звездочек в режиме IN BOOLEAN MODE.
   Волшебник
 
Модератор
23 - 30.11.05 - 23:42
Пока отбрасывание окончаний при поиске по форуму отключено.
В результате поиск значительно ускорился.
Также уменьшено его влияние на таблицу актуальных тем, т.е. основное общение.

Если будет реализована "лемматизация", то скорость поиска останется такой же высокой, но будут учитываться и словоформы. При этом увеличить размер базы, но это не проблема - места навалом.
   romix
 
Модератор
24 - 01.12.05 - 09:36
Самый "тупой" вариант - заранее составить словарь с 2 колонками вида Слово|НормальнаяФорма, например,

волшебный   волшебный  
волшебное   волшебный  
волшебного  волшебный  
волшебному  волшебный  
волшебный   волшебный  
волшебного  волшебный  
волшебное   волшебный  
волшебным   волшебный  
волшебном   волшебный  
волшебная   волшебный
волшебной   волшебный
волшебную   волшебный
волшебной   волшебный
волшебные   волшебный
волшебных   волшебный
волшебным   волшебный
волшебные   волшебный
волшебных   волшебный
волшебными  волшебный
волшебною   волшебный
волшебен    волшебный
волшебна    волшебный
волшебно    волшебный
волшебны    волшебный
волшебнее   волшебный
волшебней   волшебный
волхвующий  волшебный

Вторую колонку можно получить той самой сишной прогой, или, для надежности, любым коммерческим продуктом.
   romix
 
Модератор
25 - 01.12.05 - 09:38
Мне понравилось в словаре слово "Волхвующий". Зарегистрировать его что ли... :-)
   romix
 
Модератор
26 - 01.12.05 - 09:39
Или это заранее не подходит по каким-то причинам?
Вариант, я согласен, "тупой", и полностью в духе 1С-ника, но зато надежный/наглядный.
   Волхвующий
 
27 - 01.12.05 - 09:40
:-)
   Волшебник
 
Модератор
28 - 01.12.05 - 09:42
(26) Потому что это маразм. Основной объем базы форума придется как раз на такой словарь. Кроме того, все слова ты не составишь, их миллионы, а их словоформ десятки миллионов.

Проще учитывать вероятности сочетаний букв на границе усечения, как сделано в той сишной проге. Для расчета этих вероятностей как раз и был использован словарь из 150 тыс. слов, что достаточно много.
   Asmody
 
29 - 01.12.05 - 09:46
(28) ну, допустим, не миллионы, а несколько сотен тысяч. если, конечно, не учитывать ексерцисы базвана :)
   Волхвующий
 
30 - 01.12.05 - 09:48
(28) Слов порядка 20 тысяч (у Шекспира), словоформ *20 максимум. Я ничего не путаю? В словаре Зализняка примерно 36 тысяч словоформ. При этом, есть слова наподобие Абандон, Аббревиация и Абдоменальный (со всеми словоформами).
   Asmody
 
31 - 01.12.05 - 09:51
в словаре Даля: 2 326 221 слово, 410 556 выделенных в статьях слов, 44 694 заголовков статей
   Волхвующий
 
32 - 01.12.05 - 09:53
(31) Даль типа жжот. Что-то много миллионов слов...
   Волхвующий
 
33 - 01.12.05 - 10:01
(31) А где ты взял эту инфу? Я вижу 42554 в
http://slovari.yandex.ru
 
  AdBlock убивает бесплатный контент
   Волшебник
 
Модератор
34 - 01.12.05 - 10:02
(30) слово Построитель там есть?
   Волхвующий
 
35 - 01.12.05 - 10:11
(34) Блин Стас я имею в виду, что словарь Зализняка в его бесплатном виде несколько ограничен и местами глючен (тот же Волхвующий непонятно как затесался).

У тебя же есть сишный алгоритм кошерного обрезания слов - ты проверял, действительно так много слов? Я утверждаю что их (если убрать удаффкомовские слова с низкой частотной характеристикой) на самом деле мало (все 1С-ники тупые (с) БЖ/С).
   Волшебник
 
Модератор
36 - 01.12.05 - 10:13
(35) Могут появиться новые слова, которых нет ни в каком словаре.
   Волхвующий
 
37 - 01.12.05 - 10:15
(36) Они будут искаться, только без словоформ. Если появится "абдикционный", то ну и найдется он как написано, без словоизменения. Имхо это не страшно - гугл, например, и без руссского словоизменения все хорошо ищет...
   Волшебник
 
Модератор
38 - 01.12.05 - 10:36
(37) А функция, которую я предлагаю перевести на PHP ищет нормальную форму для любых слов. Короче, мне проще самому все сделать, чем тебя переубедить.
   Волшебник
 
Модератор
39 - 01.12.05 - 11:18
вот еще готовый алгоритм, словарь и стоп-лист для русского языка
http://snowball.tartarus.org/algorithms/russian/stemmer.html
   Волшебник
 
Модератор
40 - 01.12.05 - 11:27
накопал еще вот это "Функции mnoGoSearch для PHP"
http://www.gigo.ru/doc/php/php4/ref.mnogo.php
   Волшебник
 
Модератор
41 - 01.12.05 - 11:47
вот еще накопал открытую бесплатную поисковую систему:
http://htdig.org/
   romix
 
Модератор
42 - 01.12.05 - 12:00
(38) А вот же у них словарь стемминга:
http://snowball.tartarus.org/algorithms/russian/voc.txt

Поиск ближайшего соответствия правда не ясен, иначе как множественными селектами.
   romix
 
Модератор
43 - 01.12.05 - 12:03
(42) Слово Волшебник правда у них с глюком. :-)
   Волшебник
 
Модератор
44 - 01.12.05 - 12:04
Не нашел глюка:

волшебная                     волшебн
волшебника                    волшебник
волшебниц                     волшебниц
волшебница                    волшебниц
волшебницы                    волшебниц
волшебного                    волшебн
волшебной                     волшебн
волшебные                     волшебн
волшебств                     волшебств
   romix
 
Модератор
45 - 01.12.05 - 12:08
(44) А где ты смотришь - в ссылке по (42) или в скрипте?
Я вижу это:
...
волчьим
волшебная
волшебника
волшебниц
волшебница
волшебницы
волшебного
волшебной
волшебные
волшебств
воль
...
   Волшебник
 
Модератор
46 - 01.12.05 - 12:22
Вот сам алгоритм Snowball (перевод мой):

0. Разметка слова на части RV, R1, R2.

RV  - это часть слова, идущая после первой гласной или пустая строка, если в нем нет гласных.

R1 - это часть слова после первой согласной, следующей за гласной или пустая строка, если такой нет.

R2 - это часть слова после первой согласной, следующей за гласной в R1, или пустая строка, если такой нет.

Например:

   п р о т и в о е с т е с т в е н н о м
        |<------       RV        ------>|
          |<-----       R1       ------>|
              |<-----     R2     ------>|

Далее все шаги выполняются только над RV-частью слова.
При поиске окончания в классе всегда выбирается самое длинное.

Шаг 1: Ищем окончания PERFECTIVE GERUND. Если найдено, удаляем его и это будет конец шага 1, иначе ищем и удаляем окончания REFLEXIVE, затем ищем по очереди окончания ADJECTIVAL, VERB, NOUN. Если найдено, то удаляем их и завершаем шаг 1.

Шаг 2: Если слово окончаивается на "и", удаляем его.

Шаг 3: Ищем окончание DERIVATIONAL в отрезке R2 (т.е. все окончание должно лежать в R2), и если найдено, удаляем.

Шаг 4: Убираем двойное "н" или, если слово имеет SUPERLATIVE окончание, удаляем его и убираем двойное "н", или, если оканчивается на "ь" (мягкий знак), то удаляем его.

---
Классы окончаний

PERFECTIVE GERUND:

   группа 1:   в вши вшись

   группа 2:   ив ивши ившись ыв ывши ывшись  

   окончания из группы 1 должны следовать за "а" или "я"

ADJECTIVE:

   ее ие ые ое ими ыми ей ий ый ой ем им ым ом его ого ему ому их ых ую юю ая яя ою ею  

PARTICIPLE:

   группа 1:   ем нн вш ющ щ

   группа 2:   ивш ывш ующ  

окончания из группы 1 должны следовать за "а" или "я"

REFLEXIVE:

   ся сь  

VERB:

   группа 1: ла на ете йте ли й л ем н ло но ет ют ны ть ешь нно

   группа 2: ила ыла ена ейте уйте ите или ыли ей уй ил ыл им ым ен ило ыло   ено ят ует уют ит ыт ены ить ыть ишь ую ю  

окончания из группы 1 должны следовать за "а" или "я"

NOUN:

   а ев ов ие ье е иями ями ами еи ии и ей ей ой ий й иям ям ием ем ам ом о у ах иях ях ы ь ию ью ю ия ья я  

SUPERLATIVE:

   ейш ейше  

DERIVATIONAL:

   ост ость
   romix
 
Модератор
47 - 01.12.05 - 12:24
(46) Не осилил. Слишком много букв. :-)
А их прога вообще запускается/работает?
   Волшебник
 
Модератор
48 - 01.12.05 - 12:24
применим волшебные теги

    п р о т и в о е с т е с т в е н н о м
        |<------       RV        ------>|
          |<-----       R1       ------>|
              |<-----     R2     ------>|  

   Волшебник
 
Модератор
49 - 01.12.05 - 12:25
(47) romix, ты без словаря, как без рук. :)
 
 
   Asmody
 
50 - 01.12.05 - 12:35
(46) теперь даже я понял. пойу на 1С это все напишу
   Asmody
 
51 - 01.12.05 - 12:38
(50+) эта, а че получитца то должно?
   Волшебник
 
Модератор
52 - 01.12.05 - 12:51
(51) Вот так мы внедряем 1С... :)
   Akula
 
53 - 01.12.05 - 16:44
(0)
посмотрел программу из (21).
очень понравилась.
собираюсь разобраться как она работает и переписать ее на php.
только я вот думаю: а что скажет автор программы если кто-то без его ведома перепишет программу с C на PHP?
   Волшебник
 
Модератор
54 - 01.12.05 - 17:01
(53) Думаю, будет только рад. Если он выложил исходник программы, то тем самым опубликовал АЛГОРИТМ, а на алгоритм патентного права не бывает. Кроме того, алгоритм уже был придуман до него, он его только реализовал.

Кстати, я уже написал функцию стемминга на PHP по алгоритму Snowball (46). Работает вполне прилично, хотя на некоторых словах дает сбой. Смысловая часть занимает около 50 строчек. Осталось добавить пару колонок в таблицу, прокрутить функцию стемминга над архивом, добавить fulltext-индексы и модифицировать поисковый запрос.



Список тем форума
  AdBlock убивает бесплатный контент
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Ветка сдана в архив. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
AdBlock убивает бесплатный контент