Алгоритмы

<font face="Verdana" size="2">Originally posted by baranov:
А на сколько почти? Я что-то не знаком с ним - чайник все-таки.

Есть ли дока, или кому-нибудь не лень сюда будет реализацию на С вставить.</font>

Насчет 'почти' - для циклической суммы нереально. Я здесь привел термин 'почти' для того, чтобы показать, что у каждого слова должен быть свой уникальный код, иначе возникают коллизии. Реально же уникальный код получить сложно и больше для этого подойдет какая-нибудь хэш-функция типа MD5. Или придется разрешать коллизии.

<font face="Verdana" size="2">Originally posted by baranov:
А на сколько почти? Я что-то не знаком с ним - чайник все-таки.

Есть ли дока, или кому-нибудь не лень сюда будет реализацию на С вставить.</font>

Ссылки по теме:

http://www.zdnet.ru/pcmag/9612/129611.asp

Здесь реализация CRC32 (взята с http://klariosha.narod.ru/PN/DOC/doc-i02.htm):

u_long crc32_table[256];
/* Initialized first time "crc32()" is called. If you prefer, you can
* statically initialize it at compile time. [Another exercise.]
*/
u_long crc32(u_char *buf, int len)
{
u_char *p;
u_long crc;
if (!crc32_table[1]) /* if not already done, */
init_crc32(); /* build table */
crc = 0xffffffff; /* preload shift register, per CRC-32 spec */
for (p = buf; len &gt; 0; ++p, --len)
crc = (crc &lt;&lt; 8) ^ crc32_table[(crc &gt;&gt; 24) ^ *p];
return ~crc; /* transmit complement, per CRC-32 spec */
}
/*
* Build auxiliary table for parallel byte-at-a-time CRC-32.
*/
#define CRC32_POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */
init_crc32()
{
int i, j;
u_long c;
for (i = 0; i &lt; 256; ++i) {
for (c = i &lt;&lt; 24, j = 8; j &gt; 0; --j)
c = c & 0x80000000 ? (c &lt;&lt; 1) ^ CRC32_POLY : (c &lt;&lt; 1);
crc32_table = c;
}
}


[This message has been edited by Vyacheslav Tikhonov (edited 02-10-2001).]

[This message has been edited by Vyacheslav Tikhonov (edited 02-10-2001).]

Мда.... хотя это и ускоряет/и упрощает все - помоему не очень подходит.... как например с синонимами и словоформами быть?

А был ли опыт реализации со словарем и учетом морфологии?

PS спасибо за код....

Про хэши:

CRC32: (исходников - миллион на любом языке,

поищите, например, в google).

Для 30 миллионов слов CRC32 дает примерно

тысяч 50 коллизий. Максимальное количество

слипаний в одной коллизии ~ 150.

MD5 (исходников - тоже миллион. Я видел

даже на Smalltalk) генерит 16-байтные

ключи. Использование этого алгоритма в

поисковике - не самый лучший выбор, так как

MD5 медленный, а в 16 байт само слово обычно

влезает. Если брать первые 4 байта от MD5,

коллизий получается чуть больше, чем с CRC32.

Можно еще представить слово как число в 75-

ричной системе исчисления (33 русские

буквы+26 латинских+10 цифр + '_', апострофы

и т. д.), то в 16 байт примерно 20 букв. В

четыре байта, соответственно, 5 букв.

Поисковая машины Следопыт

(http://www.multilex.ru/sledopyt.htm)

использовала примерно такой вариант

хэширования (ну, там еще переполнение

обрабатывалось правильно).

Рамблер неизвестные слова тоже хэширует,

но очень хитро. Как - долго рассказывать.

Коллизии - бывают, не часто, но есть. Хотя

пока особо никто не жаловался, постараемся

починить в близком будущем.

С уважением,

Влад Шабанов

P.S. Если интересно, посмотрите еще

http://burtleburtle.net/bob/hash/

[This message has been edited by vs (edited 03-10-2001).]

А как обычно поступают со знакомыми словами? Словарь?

Морфология имени А. Коваленко.

См. http://linguist.nm.ru

Влад

Здорово все....

А есть ли менее комерческие реализации?

или более простые решения - по типу того, что я говорил - отбрасывать окончания и возможно суффикс за компанию....

Посмотрите, например, книжку Белоногова

(название было выше) - там написано, как

это программировать, все таблицы есть. Хотя,

конечно же, чтобы серьезно всем этим

заниматься, надо почитать вступительную

статью к словарю Зализняка, сам словарь, и

еще сколько-то книжек про русский язык

(Розенталь, ...)

Влад

Вот я наконец то и нашел кое-что:

http://speakrus.narod.ru/

главное - узнать как называется. Есть зализняк в электронном виде, что не может не радовать )

Много интересного я там нашел... множество всяких словарей и теоретического материала тоже хватает.....

http://speakrus.narod.ru/zaliznyak/zalizn.htm

Хотелось бы обсудить теперь, как это можно использовать и как удобнее всего использовать....

Например, насколько полезным может оказать ся частотный словарь или обратный?