Русская морфология

Жигaн

Новичок
Wicked
Честно говоря не вникал в твой алгоритм, т.к. getBaseForm + getAllForms тормозит нещадно ;). Предлагаю сделать так:
PHP:
$opts = array(
	// Отключим грамтаб, для скорости...
	'with_gramtab' => false,
);

$morphy = new phpMorphy(new phpMorphy_FilesBundle($dir, $lang), $opts);

function calc_distrib($ary) {
	$result = array();

	foreach($ary as $item) {
		$cnt = is_array($item) ? count($item) : 0;

		if(!isset($result[$cnt])) {
			$result[$cnt] = 1;
		} else {
			$result[$cnt]++;
		}
	}

	ksort($result);
	return $result;
}

function prepare_wf_map(phpMorphy $morphy, $words) {
	$wfs = $morphy->getAllFormsWithGramInfo($words);

	$result = array();

	// обходим результат getAllFormsWithGramInfo()
	foreach($wfs as $wf_result) {
		// Если слово найдено, результат всегда array(), иначе false
		if(is_array($wf_result)) {
			// каждое слово может иметь несколько интерпретаций
			foreach($wf_result as $wf_item) {
				// словоформа с 0 индексом - лемма (для getAllForms() неверно!)
				$base = $wf_item['forms'][0];
		
		        // идем по всем словоформам
				foreach($wf_item['forms'] as $wf) {
					$result[$wf][$base] = 1; // заносим только уникальные леммы (грамматическая инфа нас не интересует)
	    		}
	    	}
	    }
	}

	// восстанавливаем "нормальный" вид для каждого массива лемм
	foreach($result as &$bf_ary) {
		$bf_ary = array_keys($bf_ary);
	}

	return $result;

}

// $text - массив слов в windows-1251, uppercase
// $text может содержать дубликаты, на скорости в bulk mode это не сказывается (почти ;) )

// лемматизация по новому методу
$wf_map = prepare_wf_map($morphy, $text);

$bases_1 = array();
foreach($text as $word) {
	if(isset($wf_map[$word])) {
		$bases_1[$word] = $wf_map[$word];
	} else {
		$bases_1[$word] = false;
	}
}

$bases_2 = $morphy->getBaseForm($text);


var_dump(
	calc_distrib($bases_1), 
	calc_distrib($bases_2)
);
по идее дает результат 1 в 1 с getBaseForm()

Catchable fatal error: Argument 3 passed to phpMorphy_Morphier_DictBulk:hpMorphy_Morphier_DictBulk() must implement interface phpMorphy_Morphier_Interface, null given, called in C:\WWWROOT\PhpMorphy\phpmorphy-0.2.3.1\src\common.php on line 318 and defined in C:\WWWROOT\PhpMorphy\phpmorphy-0.2.3.1\src\morphiers.php on line 231
ага, спасибо! пофиксил
 

Wicked

Новичок
Ого! На такой развернутый ответ я даже не рассчитывал. Спасибо!

Если в качестве текста передаю, собственно, мой тезаурус, то статистика выводится такая:
Код:
array(6) {    array(6) { 
  [0]=>         [0]=>    
  int(43)       int(34)  + 9
  [1]=>         [1]=>    
  int(7679)     int(7776) - 97
  [2]=>         [2]=>    
  int(994)      int(949) + 45
  [3]=>         [3]=>    
  int(111)      int(71)  + 40
  [4]=>         [4]=>    
  int(7)        int(4)   + 3
  [5]=>         [5]=>    
  int(2)        int(2)   + 0
}             }
Так что, если я нигде не успел накосячить, вариант getAllForms + getBaseForm оказался лучше :) Может тебе куда-нибудь прислать мой код, подправленный твой код и, собственно, тезаурус?

Ну а так, те 9 отличий уже не шибко принципиальны, тем более, оин сводятся к одному неправильно работающему правилу и к ошибочным словам. Просто хотелось бы иметь 2 взаимозаменяемых алгоритма - для тестирования очень полезно :)

В любом случае, можно наслаждаться скоростью в 84000 слов/сек на моем Athlon 64 3500+ :) А если в этом массиве снять неоднозначность, то его даже можно подсунуть в качестве wordforms сфинксу...
 

Жигaн

Новичок
префиксное дерево строится для увеличения производительности. В phpmorphy поиск слова в словаре занимает O(N) (N - длина входного слова) время.
Если используется префиксное дерево, то сначала ищем префикс, затем от найденной позиции каждый суффикс

т.е. для этих данных
N = strlen(АБСОЛЮТНО) + strlen(ГО) + strlen(Е) + strlen(Й) + strlen(М)
Код:
[АБСОЛЮТНО]
  [0] => ГО
  [1] => Е
  [2] => Й
  [3] => М
если не использовать префиксное дерево то
N = strlen(АБСОЛЮТНО) * 4 + strlen(ГО) + strlen(Е) + strlen(Й) + strlen(М)

я там грубо строю дерево, но имхо этого хватает

про отчества попозже отвечу.

-~{}~ 08.04.08 14:58:

пришли плиз на phpmorphy at ya.ru, на моем корпусе отличий нет.
 

Wicked

Новичок
Жигaн
Я про то и говорю...
Для первого случая я насчитал
N = 45 = 7 + 3 + 8 + 1 + 2 + 9 + 2 + 1 + 1 + 1 + 9 + 1,
а для второго
N = 19 = 7 + 1 + 2 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1.
Или я как-то не так считал, и в первом случае "указатели" тоже могут быть эффективно переиспользованы?

-~{}~ 08.04.08 19:05:

Послал.

-~{}~ 09.04.08 18:00:

http://en.wikipedia.org/wiki/Radix_tree - вот в таком виде в идеале нужно представлять дерево для минимизации кол-ва циклов в walk(). Сначала считаем путь до "абсолют". Указатель переиспользуем для получения "абсолют[н]". Этот указатель переиспользуем для получения "абсолютн[ая|о|ы]" ... и т.д.

Ну а вообще я посмотрел, как устроены fsa_*_mem::walk(). На мой взгляд там напрашивается кэширование вида:
$this->c[$prev_trans][$char] = $trans. Надо будет проверить
 

Жигaн

Новичок
Имхо начинать надо с выключенным предсказанием.
PHP:
$opts = array(
'predict_by_suffix' => false, 
'predict_by_db' => false
);
в этом случае, результат получается такой идентичным getBaseForm().

Если включить предсказание, отличия будут в любом случае. К примеру в тезаурусе есть три словоформы ПСЕВДОЕВКЛИДОВА, ПСЕВДОЕВКЛИДОВО, ПСЕВДОЕВКЛИДОВОМ

предсказываются getBaseForm как:

ПСЕВДОЕВКЛИДОВА => ПСЕВДОЕВКЛИДОВ (Сущ), ПСЕВДОЕВКЛИДОВЫЙ(Прил)
ПСЕВДОЕВКЛИДОВО => ПСЕВДОЕВКЛИДОВЫЙ(Прил), ПСЕВДОЕВКЛИДОВО(Сущ)
ПСЕВДОЕВКЛИДОВОМ => ПСЕВДОЕВКЛИДОВОЙ(Сущ), ПСЕВДОЕВКЛИДОВЫЙ(Прил)

если взять из хэша словоформ то:
ПСЕВДОЕВКЛИДОВА => ПСЕВДОЕВКЛИДОВ, ПСЕВДОЕВКЛИДОВЫЙ, ПСЕВДОЕВКЛИДОВО
ПСЕВДОЕВКЛИДОВО => ПСЕВДОЕВКЛИДОВЫЙ, ПСЕВДОЕВКЛИДОВО
ПСЕВДОЕВКЛИДОВОМ => ПСЕВДОЕВКЛИДОВОЙ, ПСЕВДОЕВКЛИДОВЫЙ, ПСЕВДОЕВКЛИДОВО

видим лишнюю форму ПСЕВДОЕВКЛИДОВО у 1 и 3.

Взялась она отсюда:
ПСЕВДОЕВКЛИДОВО(Сущ) имеет формы ПСЕВДОЕВКЛИДОВА, ПСЕВДОЕВКЛИДОВОМ

соответственно, в хэш для словоформ ПСЕВДОЕВКЛИДОВА, ПСЕВДОЕВКЛИДОВОМ попадает лишняя лемма ПСЕВДОЕВКЛИДОВО

Поэтому, имхо мы ничего не теряем. Т.к. кол-во лемм выданных getBaseForm() равно кол-ву лемм полученных из хэша. Интересный момент получается с разным количеством словоформ с нулевым количеством лемм. Получается так: некоторые словоформы предсказываются таким образом, что в результате среди всех форм нет искомой. Пример: КАРПЕЛЕВИЧА => лемма КАРПЕИЙ, кандидат КАРПЕЬЕВИЧА, тут баг в алгоритме построения индекса для предсказания. у aot баг тоже есть, но выражается иначе: все словоформы = КАРПЕЛЕВИЧА ;)

Для первого случая я насчитал
N = 45 = 7 + 3 + 8 + 1 + 2 + 9 + 2 + 1 + 1 + 1 + 9 + 1,
а для второго
N = 19 = 7 + 1 + 2 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1.
Чето странно, считать нужно так:
PHP:
// N
$N = strlen(implode(array_keys($prefixes)));
foreach($prefixes as $suf_ary) {
	$N += strlen(implode($suf_ary));
}

// вызовы $fsa->walk
$walk_calls = count($prefixes, COUNT_RECURSIVE);
http://en.wikipedia.org/wiki/Radix_tree - вот в таком виде в идеале нужно представлять дерево для минимизации кол-ва циклов в walk(). Сначала считаем путь до "абсолют". Указатель переиспользуем для получения "абсолют[н]". Этот указатель переиспользуем для получения "абсолютн[ая|о|ы]" ... и т.д.
Я сначала так и сделал, но здесь важен баланс, если использовать полноценное дерево, то вырастает $walk_calls, что снижает производительность (нафиг вызывать $fsa->walk() для одного символа?) + надо учитывать, что строить многоэтажные хэши накладно. В итоге этот метод оказался более медленным.

Ну а вообще я посмотрел, как устроены fsa_*_mem::walk(). На мой взгляд там напрашивается кэширование вида:
$this->c[$prev_trans][$char] = $trans. Надо будет проверить
Нет это не покатит, у меня был кэш в версии 0.1, типа $cache[$input_word_prefix] => $trans, было нормально, но там и автомат несколько иного вида был.. Попробовал сделать так:
PHP:
			if(!isset($this->cache[$prev_trans][$char])) {
				list(, $trans) = unpack('V', 
substr($mem, $fsa_start + ((($trans >> 10) + $char + 1) << 2), 4));
				$this->cache[$prev_trans][$char] = $trans;
				$this->misses++;
			} else {
				$trans = $this->cache[$prev_trans][$char];
				$this->hits++;
			}
Скорость упала так:
PHPMORPHY_STORAGE_FILE 1100 => 1000
PHPMORPHY_STORAGE_MEM 2600 => 1300
PHPMORPHY_STORAGE_SHM не пробовал должно быть похоже на PHPMORPHY_STORAGE_MEM

соотношение hits/misses ; cache_size = count($cache, COUNT_RECURSIVE)
1000 слов = 0.76; 6588
5000 слов = 1.45; 25464
10000 слов = 1.92; 43142
17000 слов = 2.46; 63404

имхо, не стоит оно того

Да, насчет отчеств. Попробовал сгенерить словарь для предсказания с длинной суффиксов = 7, немного помогло.
получил КАРПЕЛЕВИЧА => КАРПЕЛЬ , почему нет ;)
 

Wicked

Новичок
Чето странно, считать нужно так:
...
Я сначала так и сделал, но здесь важен баланс, если использовать полноценное дерево, то вырастает $walk_calls, что снижает производительность (нафиг вызывать $fsa->walk() для одного символа?) + надо учитывать, что строить многоэтажные хэши накладно. В итоге этот метод оказался более медленным.
Помеченное жирным - неверно. Почему - пусть скажет код :) Надеюсь, ты поймешь, почему я считаю именно так:
http://phpclub.ru/paste/index.php?show=2039

Единственное, что я не учел, так это то, что в моем случае еще потребуется расставлять метки завершения слова: например, префикс "абсолют" является еще и самостоятельным словом.

-~{}~ 10.04.08 09:46:

соотношение hits/misses ; cache_size = count($cache, COUNT_RECURSIVE)
1000 слов = 0.76; 6588
5000 слов = 1.45; 25464
10000 слов = 1.92; 43142
17000 слов = 2.46; 63404
вот... а если теперь убрать построение префиксного дерева, которое у нас как бы тоже является кэшем?

у меня на 8836 словах хиты достигли 74.83% (h/m = 2.97) и findWord работал 0.60 вместо, а 0.67 сек.
cache size = 29325.
PHPMORPHY_STORAGE_MEM.

-~{}~ 10.04.08 10:03:

Имхо начинать надо с выключенным предсказанием.
в этом случае, результат получается такой идентичным getBaseForm().
да

когда включаю predict_by_suffix, результат остается идентичным.

когда включаю predict_by_suffix и predict_by_db, результаты расходятся в 9 словах - http://phpclub.ru/paste/index.php?show=2037. Проблем с "ПСЕВДОЕВКЛИДОВОМ" не испытываю, и вообще не очень понял, к чему ты про него так много расписал - у меня и getBaseForm, и хэш для него возвращают только 2 формы:
'ПСЕВДОЕВКЛИДОВОМ' =>
array (
0 => 'ПСЕВДОЕВКЛИДОВОЙ',
1 => 'ПСЕВДОЕВКЛИДОВЫЙ',
),

-~{}~ 10.04.08 16:39:

Кстати, я тут, оптимизируя свои алгоритмы, пришел к выводу, что лучше бы bulk getBaseForm() возвращал значения в виде флипнутых ассоциативных массивов с базовыми формами в ключах вместо нумерованных.
 

Жигaн

Новичок
Да, насчет дерева, я облажался ;). Вот два варианта: http://phpclub.ru/paste/index.php?show=2040, как ты предлагал. Имхо лучший №2

вот... а если теперь убрать построение префиксного дерева, которое у нас как бы тоже является кэшем?
а зачем его убирать? Я мерил в цикле getBaseForm() (сейчас попробовал в bulk mode, скорость стабильно падает на 1000 слов). Кстати меряю я не профайлером, а скорость лемматизации - getBaseForm, может быть, поэтому у нас расхождение такое получилось?

у меня и getBaseForm, и хэш для него возвращают только 2 формы:
'ПСЕВДОЕВКЛИДОВОМ' =>
array (
0 => 'ПСЕВДОЕВКЛИДОВОЙ',
1 => 'ПСЕВДОЕВКЛИДОВЫЙ',
),
Хм, странно... Может словари разные, у меня за декабрь 2007.

Кстати, я тут, оптимизируя свои алгоритмы, пришел к выводу, что лучше бы bulk getBaseForm() возвращал значения в виде флипнутых ассоциативных массивов с базовыми формами в ключах вместо нумерованных.
Ээ, типа такого
array(
'ПСЕВДОЕВКЛИДОВОМ' => array(
'ПСЕВДОЕВКЛИДОВОЙ' => true, 'ПСЕВДОЕВКЛИДОВЫЙ' => true
)
? А смысл?
 

alekciy

Новичок
Сергей Тарасов
Модуль под PHP? А начем планируется его писать? С?
 

Alexandre

PHPПенсионер
Сергей Тарасов экстеншены принято писать на Си, чтоб можно было их везде скомплировать.
хорошая мысль +1
Сергей, если возмешься - я тебе помогу
 

Alexandre

PHPПенсионер
это ты в свой маке добавишь - и проблем не будет.
а в чужой кто добавит, если его конфигуре генерит.
 

Wicked

Новичок
Жигaн
1) Вообщем производительность меня в целом устраивает :) Если мне не будут за раз загружать целые тезаурусы предметных областей, то инкрементально пополнить кэш - дело пустяковое.

2)
А если в этом массиве снять неоднозначность, то его даже можно подсунуть в качестве wordforms сфинксу...
оказалось даже необязательно, т.к. я сделал такую штуку:
из неоднозначного отображения, коим является getBaseForm() получилось сделать 2 других отображения:
а) однозначное, которое используется при индексации, и которое вполне подходит для использования в рамках сфинковских wordforms.
б) неоднозначное, чуть более "громоздкое", чем оригинальное, которое используется при поиске.
Получилось довольно замысловато, поэтому расписывать не буду. Если кому интересно: обращайтесь в аську - расскажу.

3) Можешь рассказать, откуда появляются новые словари? Также интересует процесс добавления нового языка. Можно ли использовать, например, без особых приседаний конвертировать словари от ispell? Получится, конечно, для галочки, но это лучше, чем ничего. Насколько я представляю себе структуру словарей ispell и aot, то они доволько похожи. Интересует реальный опыт.

2all
Если уж оформлять в виде экстеншена, то тогда уж наверное полезней было бы сделать c/c++-библиотеку + extension.
 

Alexandre

PHPПенсионер
Если уж оформлять в виде экстеншена, то тогда уж наверное полезней было бы сделать c/c++-библиотеку + extension.
ну это более правильно, делается libmorf
а на нее пишется враппер на пхп
кажется на офф. сайте "русск. морфологии" на сях уже что-то написано.
 

Farsh

~ on ~ high ~ wave ~
народ , сорри что чуть чуть не в тему , но хоть кто нибудь пробовал работать с морфологией АОТ в связке с php ? Там есть пример на python :
http://www.aot.ru/docs/morphexam_python.htm , но я в нем далек ;(
 

berkut

Новичок
под виндой роняет апач при использовании разделяемой памяти в качестве хранилища
 

Жигaн

Новичок
Wicked
1) Это хорошо ;), я сделал версию с использованием patricia в пакетном режиме, оно дает прирост ~10%, скоро выложу на sf.

3) Все словари которые есть сейчас, я брал от aot. С новыми словарями проблема такого плана: у aot в коде зашито три кодировки 1250, 1251, 1252, причем сделано это достаточно криво (к примеру в кодировке 1251 не воспринимаются украинские символы). Потому
надо сделать:
a) новый компилятор словаря без зависимостей от aot. Готово на ~80%.
b) Т.к. MorphWizard от aot работать не будет, нужно сделать подобную утилиту, возможно с веб интерфесом.
c) конвертеры из myspell (т.к. есть большое количество уже готовых словарей от openoffice - http://wiki.services.openoffice.org/wiki/Dictionaries), aot форматов. Это готово на 100%.

Сергей Тарасов
Есть несколько вариантов:
1) Использовать код aot, но тогда привязываемся только к тем словарям которые есть у aot. Еще падать может иногда ;)
2) Использовать код с http://lemmatizer.org , потенциально есть возможность добавить новые языки. Тут самый главный недостаток такой: предсказание у меня и в коде http://lemmatizer.org работает по-разному, придется подтачивать..
3) Писать все свое. У меня есть либа для доступа к конечному автомату, сделать все остальное достаточно просто. Потом сделать биндинги и все ;). Вообще неплохо еще иметь cli приложение, чтобы не валить веб сервер ;).

Я больше склоняюсь к третьему варианту.

Хм... самый, на мой взгляд, большой вопрос, это где и в каком виде хранить словарь???
А чем файловая система не устраивает?

[Farsh]
Там используется com объект(он платный у aot, стоит 250$, работает под виндой ;)) В пхп можно использовать при помощи http://de.php.net/manual/ru/book.com.php

[berkut]
Спасибо. А shmop_* функции работают вообще? И версия пхп какая?
 
Сверху