Как из слова или фразы получить все возможные варианты написания?

[tashkentchi]

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

Надо поэкспериментить.

 

[StUV]

имхо, задача реашется с помощью 10-ти средних "жестянщиков-сборщиков", классифицирующих всевозможные варианты - ессно, если бюджет проекта позволяет =)

 

[tashkentchi]

У нас в конторе труд "вбивальщиков" полуавтоматизирован. Программно ищутся наилучшие соответствия записей в базе строкам прайслистов. Это дело выдается "вбивальщику", чтобы он руками исправил всякие конфузы и указал, что делать с позициями, не найденными в базе. Потом все это оптом сохраняется.

Не могу сказать, что эта система работает идеально. "Вбивальщики" сидят на выработке (сумма количеств позиций обработанных прайсов) и мусор лезет в базу тоннами. Причем, если с жестянщиками еще можно как-то ладить, то с аптекарями - проще убить себя ап стену

-~{}~ 20.03.08 04:23:

Вобщем, с фултекстом все оказалось не просто. Создал таблицу

[sql]CREATE TABLE test_goods (
id int(11) NOT NULL auto_increment,
name varchar(255) NOT NULL,
normalize text NOT NULL,
PRIMARY KEY (id),
FULLTEXT KEY normalize (normalize)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;[/sql]
Пихнул в нее ок. 40 тыс. наименований товаров из реальной базы. Запросы

[sql]SELECT name, normalize, MATCH(normalize) AGAINST('$search') AS rank
FROM test_goods
WHERE MATCH(normalize) AGAINST('$search') > 10
ORDER BY rank DESC
LIMIT 30[/sql]
Выполняются порядка 0,001-0,01 сек. Это на девелоперской машине 3GHz, память 1GB, Linux 2.6.23.15, MySQL 5.0.45.

Теперь про качество результатов:

Если не пользовать условие

[sql]MATCH(normalize) AGAINST('$search') > 10[/sql]
то в результат попадает куча мусора.
Так, например, на запрос "фартук", помимо собственно фартуков выдается еще и

Штукатурка CRAUZIT SF-04
Мыло хозяйственное 60%(тыс. штук)
Фармадекс 0,1%р-р 10мл
и т.п.

Однако с указанным условием мусор не встречается; на просьбу фартуков, выдаются только фартуки

А на запрос "Sony DVD" получил следующие записи:

Видеокамера SONY DVD305
DVD-RW SONY DL box
Цифровая видеокамера SONY DVD505
Диск DVD-RW Sony
Диск DVD-R Sony
DVD±RW Sony 16x Box
DVD±RW Sony DRU-810A DL Box
DVD±RW Sony DW-Q120A DL OEM
DVD±RW Sony DRU-820A 16x DL Box
Диск DVD-R Sony LG 4.7GB 10шт
DVD±RW Sony DRU-830AK 16x DL/RAM Box
DVD±RW Sony DW-Q30A DL Silver OEM
DVD±RW Sony DWG-120A DL Silver OEM
Проигрыватель Sony MPEG4-558 DVD Retail
DVD+RW+DL SONY DRU-840AK Black 20-/20+R/8DL-/8DL+R/6-/8+RW/16x, RAM/12,48/32/48x

Но на запрос "Sony" при указанном условии не получил ни одной записи, а без этого условия - 30 релевантноых записей.

Поскольку не могу себе представить разумный способ выбора ограничения для различных запросов, то идею придется отставить

 

[Wicked]

tashkentchi
http://yurikhan.livejournal.com/29451.html

 

[tashkentchi]

Оч интересная статья.
Но там структура базы оптимизируется под запросы вида "*строка*", обычные при поиске файлов. А поиск по товарной базе имеет свою специфику.

Кроме того, автор отказался от fulltext-а на следующем основании:

Угу. Только полнотекстовый поиск требует, чтобы слова разделялись пробелами или хотя бы знаками препинания. А в именах файлов слова обычно не разделяются никак, или разделяются знаком _, или CamelCase’ом. Придумывать разбивалку слов, хранить рядом разбитую строку, иметь по ней полнотекстовый индекс — можно, но очень влом и всё равно всех случаев не предусмотришь.

А я предлагаю элементарный способ разбивки, который реализовать не влом. Вот код пхп, который ее реализует (для UTF8):

$str = 'DVD±RW Sony DRU-810A DL Box';

$str = preg_replace("'[^A-zА-я0-9]'u", ' ', $str);
$str = preg_replace("'\s+'u", ' ', $str);
$str = strtolower(iconv('UTF8', 'CP1251', $str));
$str = explode(' ', $str);
foreach ($str as $k => $v) {
    $len = strlen($v) - 1;
    if (3 > $len) {
        if (2 > $len) {
            unset($str[$k]);
        }
        continue;
    }
    $str[$k] = '';
    for ($i = 1; $i < $len; ++$i) {
        if ($str[$k]) {
            $str[$k] .= ' ';
        }
        $str[$k] .= $v{$i-1} . $v{$i} . $v{$i+1};
    }
}
$str = implode(' ', $str);
$str = iconv('CP1251', 'UTF8', $str);

Выполнение этого кода при инсерте/апдейте товаров не потребует больших ресурсов.

Ну так вот, насчет поиска:

IN BOOLEAN MODE мне сильно помог.

Нормализуем искомую строку так: "Sony DVD" => "+son +ony +dvd".
И пользуем такой запрос:

[sql]SELECT name, normalize, MATCH(normalize) AGAINST('$search') AS rank
FROM test_goods
WHERE MATCH(normalize) AGAINST('$search' IN BOOLEAN MODE)
ORDER BY rank DESC[/sql]

Ищет достаточно быстро (0.001-0.02 сек. на указанной выше таблице) и никакого мусора! Во всяком случае, я не сумел придумать строку, на которую получил бы нерелевантный результат.

 

[Alexandre]

у меня в конторе поиск по БД товаров (более млн поз, планируется до 5-ти) занимает две навороченные sql процедуры, и то - он не идеален и будет переделываться в ближайшем будущем.

а сфинкс прикрутить не пробовали?

 

[tashkentchi]

Залез в гугл - узнать что такое сфинкс Имеется в виду это: http://www.sphinxsearch.com/ ?
Очень интересно, изучаю.

 

[Alexandre]

Очень интересно, изучаю.

и правильно, на сегодня самая эффективная локальная поисковая машина.