В базе есть три типа слов:
1. Слова без базовой строки. Базовая строка это псевдооснова слова, то к чему прибавляются окончания. Слова без псевдоосновы это например, “идти”, это может преобразовываться в “шел, шла, шли” и прочее. Таких слов около сотни, а их морфологических форм чуть больше 1000. Это довольно часто употребляемые слова, например, местоимения. Поэтому не учитывать их нельзя.
2. Нормальные слова. У которых есть псевдооснова.
3. Слова существующие только с приставкой. Если их опустить, особых проблем не будет. Они довольно редко используются. Я их рассматривать не буду.
Поиск в базе является ключевым моментом производительности.
Теперь три основных задачи поиска:
1. Поиск одной формы слова. Применяется, когда мы хотим проверить слово на правильность.
2. Поиск всех возможных морфологических неоднозначностей. Он аналогичен первому варианту.
3. Поиск корректоров. Когда в ворд мы нажимаем правую кнопку мыши на подчеркнутом красным словом, то он выводит список на что это слово нужно заменить. Производительность этого метода не важна, посколько пользователь не заметит происходит он за одну тысячную секунды или за одну пятую. Такое свойство человеческого восприятия.
Остановимся на первом варианте, второй по аналогии, а оптимизация третьего не нужна.
1. Слова без базовой строки.
По ним необходимо искать сначала. Поискольку их мало (со всеми словоформами около 1000) то при загрузке можно тупо создать массив их контрольных сумм, массив номеров и массив номеров их флексиа моделей (форм слова). Потом его упорядочить по контрольным суммам и искать по нему. На базу мы потратим где-то 10 лишних КБ в памяти. Поскольку слов 1000, а чек сумм имеет длину 32 бита (в худшем случае), то можно искать тупо по чек суммам бинарным поиском.
Функцию быстрой сортировки напишу ниже. Функцию чек сумм не буду писать, по своим личным соображениям. Но ее легко написать.
for (int i= 0; i
}
W1FMcount++;
Out.W1QMassCount=W1FMcount;
Out.W1QMassCS = new long [W1FMcount] ;
Out.W1QMass_FM_Num = new long[W1FMcount];
Out.W1QMass_Num = new long[W1FMcount];
long num=0;
for (int i= 0; i
{
Out.W1QMass_FM_Num[num]=j;
Out.W1QMass_Num[num]=i;
Out.W1QMassCS[num]=GetWordCheckSumInt64YOvE(Out.Words1[i].FM->Ss[j]);
num++;
}
int dfsdf=0;
}
QSort3(Out.W1QMassCS, Out.W1QMass_FM_Num, Out.W1QMass_Num, 0, num++);
Теперь остановимся на бинарном поиске. Смысл такой, если массив упорядочен, и состоит из N элементов. То проверяем элемент с индексом N/2. Если искомое меньше этого элемента, то можно однозначно сказать, что искомый элемент находиться в первой половине. От 0 до N-1;, если больше то во второй. И так отсекаем половины, пока не находим искомый элемент или не убеждаемся, что его нет.
long QFind(long ID,long * IDs,long N)
{
long first = 0;
long last = N;
long cur;
while(first<=last) { cur = (first+last)/2; if(IDs[cur]==ID) return cur; else if(IDs[cur]>ID)
last = cur-1;
else
first = cur+1;
}
return -1;
}
С поиском по словам первого типа мы разобрались. Теперь по второму типу. Есть два момента. Первый это формирование индексов.
К сожалению мы не можем сформировать нормальный хеш, поскольку слова имеют очень много окончаний. Поэтому мы сформируем каличную версию хеша, по первым двум буквам BaseStr (базовой строки, псевдоосновы). При загрузке:
для каждого слова второго типа формируем.
long I = (byte)Link[i][0];
I-=192;
if (Link[i][0]=='Ё')
I=35;
long J = (byte)Link[i][1];
J-=192;
if (Link[i][1]=='Ё')
J=35;
if (I>-1&& I<37>-1&& J<37) i="I*36+J;" 1000="" 100="" __int64="" 33="" 6="" 64="" __int16="" __int32="" 4="" 5="" i4="" i3="" 10="" min="" 2="" s2="=NULL)" for="" int="" i="(Номер_первого_символа" char="" 0="" c2="S2[i];" return="" if="" c1="S1[i];">c2)
{
if (c1!='-')//в базе дефис это исключение при сортировке
return 1;
else
return -1;
}
else
{
if (c2!='-')
return -1;
else
return 1;
}
}
else if (c1==' ')
return 0;
}
//Ограничитель на вверх -1
//Ограничитель вниз 1
}
Если эта функция возвращает 2 и -1, то возможно мы нашли искомое словарное слово.
Если эта функция возвращает -2, то это значит неопределеность
-1 - слово в первой часте
1 - слово во второй часте
Функция сравнения слова со словарным
int CheckWord(char * Find, int len, MorfBase * MB,long num, bool OnlyBaseForm=false) { //OnlyBaseForm==true сверка только по базовой форме слова. Нужно при загрузке базы синонимов if ((MB->Words2[num].MaxLen
FindWord FindWordW2(char * Find, int len, MorfBase * MB,bool OnlyBaseForm=false) { FindWord Out; Out.BaseNum=-1; //return Out; long I = (byte)Find[0]; I-=192; long J; if (len>0) J= (byte)Find[1]; else J=0; J-=192; long I0=-1; long I2=-1; if (Find[0]==’Ё’) I=35; if (len>0&&Find[1]==’Ё’) J=35; if (I>-1&& I<37>-1&& J<37) x =" I*36+J;" i0 =" MB-">W2I[X]; I2 = MB->W2Iend[X]; } //Считаем индекс в базе long first = I0; long last = I2+1; long cur;//= (first+last)/2; if (I0!=-1) { while(first<=last) { cur= (first+last)/2; int res = StrCompMy(Find,MB->Words2[cur].BaseStr); Point121: if (res==2||res==0) { res=CheckWord(Find, len, MB,cur,OnlyBaseForm); //возращает -2, если не найдено или номер словоформы if(res!=-2) { Out.BaseNum=2; Out.WordNum=cur; Out.LemmaNum=res; return Out; } if (first==last) return Out; } if(res==-2)//здесь не должно быть елсе {//Линейный поиск по соседним элементам for(int i=1;;i++) { if (cur+i<=last) { res=StrCompMy(Find,MB->Words2[cur+i].BaseStr); if (res!=-2) { cur=cur+i; goto Point121; } } if (cur-i>=first) { res=StrCompMy(Find,MB->Words2[cur-i].BaseStr); if (res!=-2) { cur=cur-i; goto Point121; } } if (cur+i>last||cur-i
Есть еще момент того, что проверка морфологии много раз запускаеться по практически одному и тому же самому тексту, когда этот текст редактируеться. Для предварительного поиска можно использовать рандомные бинарные деревья или РБ-Деревья или хеши. Или и деревья и хеши. Но можно поступить иначе - не запоминать отдельные слова, а шинглы по пять слов и результаты для каждого слова. Естестевенно эти шинглы должны считататься без морфологии. Для мы получим улучшение производительности в 5 раз (слова проверяються по пять штук).
Можно еще больше ускорить поиск. Формировать одновременно и последовательную (неупорядоченную) и упорядоченную базу(бинарное или РБ Дерево). Сначала шингл I сверяеться с итым элементом в в последовательной базе, потом с I-1, потом с I+1. Если до этого не было вставки двух и более слов, то мы найдем шинг. Если не нашли, то запускаем бинарный поиск.
Но первый вариант (без шинглов) позволит ускоряться при повторении слов в тексте.
P.S. Думаю сделать публичную DLL библиотеку по морфологии. Бесплатную.
Но для работы приложения потребуется сначала установить генератор.
Если кому то это интересно - напишите мне по мылу.BELOUSOV SOBAKA altalabs.ru
P.P.S. Я так подумал, можно перенести из первой базы во вторую пару тысяч самых распространенных слов по частотному словарю. Это должно хорошо устроить работу. Поскольку я читал что 3000 слов перекрывают 90% словоиспользований. Для меня как для русского человека, этот факт печален - такой маленький словарный запас у людей.
