В первой части этого описания попытки решения интересной конкурсной задачи я рассказал о подготовке данных для анализа и о нескольких экспериментах. Напомню, условие задачи заключалось в том, чтобы с наибольшей вероятностью определить наличие слова в словаре, не имея доступа к этому словарю в момент выполнения программы и с ограничением на объем программы (включая данные) в 64K.
Как и в прошлый раз, под катом много SQL, JS, а также нейронные сети и фильтр Блума.
Напомню, последним описанным экспериментом была попытка решить задачу через построение дерева принятия решения. Следующей проверяемой технологией был алгоритм поиска взаимосвязей, входящий в пакет Microsoft Data Mining. Вот так выглядит результат его работы:
На картинке видно, что алгоритм нам показывает, что, по его мнению, если в слове 6 гласных и отсутствуют буквы "Z","X" и "J", то с вероятностью 97,5% слова нет в словаре. Проверяю, сколько тестовых данных покрывают все правила – оказывается, что большую часть. Радуюсь результату, беру правила, переключаюсь из DataGrip в WebStorm и пишу JS-код.
Код для проверки выглядит так:
var wordStat=getWordStat(word);
var wrongRules=0;
var trueRules=0;
function getWordStat (word)
{
//Считаем гласные и согласные
var result={vowels:0,consonants:0};
for (var i=0;i<word.length;i++)
{
result[word[i]]=result[word[i]]?(result[word[i]]+1):1;
if ('aeiouy'.indexOf(word[i])>-1)result.vowels++;
else if (word[i]!="'")result.consonants++;
}
return result;
}
for (i=0;i<rules.length;i++)
{
var passed=0;
var rulesCount=0;
for (var rule in rules[i]){
rulesCount++;
if((wordStat[rule.toLowerCase()]?wordStat[rule.toLowerCase()]:0)==rules[i][rule])passed++;
}
if (passed==rulesCount&&rulesCount!=0)
{
return false;
}
}
Об упаковке данных пока не думаю, просто строю в экселе json типа
var rules= [
{"Consonants":6,"H":0,"X":0,"J":0},
{"Consonants":6,"H":0,"V":0,"Q":0}
]Очередной "момент истины"… И очередное разочарование — 65%. Ни о каких 97.5% речь не идёт.
Проверяю, сколько данных и как отсеивается именно правилами – получаю много и ложноотрицательных и ложноположительных срабатываний. Начинаю понимать, в чём были два моих основных "прокола". Я не учёл повторы слов и пропорции массивов. Т.е.:
1) изначально предположил, что вероятность проверки на тестовых словах совпадёт с вероятностью в тестовых наборах. Но слова в тестовых наборах повторяются и эти повторы сильно снижают картину, если я на этих словах ошибаюсь. Кстати, сразу появляется мысль считать все повторяющиеся слова правильными.
2) алгоритмы майнинга сделали всё правильно: они увидели на миллион неправильных слов десять тысяч правильных и обрадовались вероятности в 99%. Неправильно сделал я, скормив алгоритму несоизмеримые объемы правильных и неправильных слов. Например, проверяем указанное выше правило {"Consonants":6,"H":0,"X":0,"J":0}:
select isvalid,count(*) from formining10 where Vowels=6 and Z=0 and X=0 and J=0
group by isvalid| isValid | count |
|---|---|
| 0 | 5117424 |
| 1 | 44319 |
Действительно, разница больше, чем в 100 раз, и алгоритм её распознал правильно. Но я-то не могу проигнорировать 44К правильных слов, т.к. при проверке пропорции будут примерно равны. Значит, и скармливать надо одинаковые по размеру массивы правильных и неправильных слов. Но ведь 600К неправильных слов будет мало… Беру другие 10М тестовых слов, но уже с повторами, т.е. не удаляя ни положительные, ни отрицательные дубликаты. Единственное, что делаю – убираю "мусор" через описанные в первой статье фильтры (несуществующие пары/тройки). Скармливаю майнингу… Увы, адекватных правил он при таком раскладе не находит, а при попытке построить дерево решений, говорит, что ничего хорошего не обнаружил. Напомню, все "очевидные" неправильные варианты я отрезал ещё до скармливания данных майнингу через неправильные пары/тройки.
Возвращаюсь к "описательному" методу.
Напомню, в первой части статьи для майнинга я создал на основании словаря таблицу, у которой строка соответствует слову, столбец – номеру символа в слове, а значениями ячеек является порядковый номер буквы в алфавите (27 для апострофа). Из этой таблицы я делаю "карту" для каждой длины, т.е. для какой длины на каком месте не может встречаться та или иная буква. Например, "7'4" означает, что в словах из семи букв апостроф не может быть четвёртым символом, а "15b14" означает, что в словах из 15 букв "b" ни разу не была замечена предпоследней.
Создаём таблицу с позициями букв для каждой длины слова
select length=len(word),'''' letter, charindex('''',word) number into #tmpl from words where charindex('''',word)>0
union
select length=len(word),'a' letter, charindex('a',word) number from words where charindex('a',word)>0
...
union
select length=len(word),'z' letter, charindex('z',word) number from words where charindex('z',word)>0Делаем декартово произведение букв, длин и позиций, а затем left join на существующие
select l.length,a.letter,l.length from allchars a
cross join (select 1 number union select 2 union select 3 union select 20 union select 21) n
cross join (select 1 length union select 2 union select 3 union select 20 union select 21) l
left join #tmpl t on a.letter=t.letter and t.number=n.number and t.length=l.length
where t.letter is not nullДальше дополняем номером позиции в слове "урезанную" полумеру из первой части для проверки несуществующих комбинаций из двух и трёх символов в слове.
Выбираем пары и тройки:
--Таблицы с результатом. cright и cwrong – количество правильных и неправильных слов.
create table stat2(letters char(2),pos int,cright int,cwrong int)
create table stat3(letters char(3),pos int,cright int,cwrong int)
create table #tmp2(l varchar(2),valid int,invalid int)
create table #tmp3(l varchar(3),valid int,invalid int)
--Пары
declare @i INT
set @i=0
while @i<20
begin
set @i=@i+1
truncate table #tmp2
truncate table #tmp3
--неправильные
insert into #tmp2
select substring(word,@i,2),0,count(*)
from wrongwords
where len(word)>@i
group by substring(word,@i,2)
--правильные
insert into #tmp3
select substring(word,@i,2),count(*),0
from words
where len(word)>@i
group by substring(word,@i,2)
insert into stat2
--результат
select e.letters2,@i,r.valid,l.invalid
from allchars2 e
left join #tmp2 l on l.l=e.letters2
left join #tmp3 r on r.l=e.letters2
end
declare @i INT
set @i=0
while @i<19
begin
set @i=@i+1
truncate table #tmp2
truncate table #tmp3
--неправильные
insert into #tmp2
select substring(word,@i,3),0,count(*)
from wrongwords
where len(word)>@i+1
group by substring(word,@i,3)
--правильные
insert into #tmp3
select substring(word,@i,3),count(*),0
from words
where len(word)>@i+1
group by substring(word,@i,3)
--результат
insert into stat3
select e.letters3,@i,r.valid,l.invalid
from allchars3 e
left join #tmp2 l on l.l=e.letters3
left join #tmp3 r on r.l=e.letters3
print @i
end
Копирую результат в эксель, играю с количеством в правильных и неправильных словах, оставляю только теоретически наиболее вероятные (встречается минимум у 5-10 слов) и наиболее полезные (соотношение правильно/неправильно минимум 1:300).
Делаю сводную таблицу. Результат выглядит так:
Делаю данные для программы: пара + битовая маска (см. формулу вверху картинки).
Код загрузки аналогичен описанному в первой части, а вот проверка меняется.
for (letters in letters2Map)
{
if (word.indexOf(letters)>=0) {
if ((letters2Map[letters] & 1) ==1)
{
result = return false;
}
for (var k=0;k<21;k++)
{
if (((letters2Map[letters] & Math.pow(2,k+1))==Math.pow(2,k+1))&& (letters[0] == word[k-1]) && (letters[1] == word[k]))
{
return false;
}
}
}
}
Проверяю: опять не больше 65%. Возникает желание немного "схитрить" и улучшить результат, опираясь на логику работы генератора:
- Считать все повторы правильными словами, т.к. неправильные повторяются намного реже. Есть какие-то странные явные лидеры по повторам среди неправильных, но их можно просто описать как исключения.
- Следить за пропорциями правильно/неправильно в пакетах из 100 слов и выравнивать их после перекоса 60/40.
Но оба этих варианта a) ненадёжные и б) "неспортивные", поэтому оставляю их на потом.
Хочу сделать последнюю проверку без ограничения на объем данных, чтобы убедиться в том, что "описательным" способом решить задачу невозможно. Для этого решаю к проверкам добавить все "соседствующие" пары и тройки символов. Начинаю с пар, наполняю таблицу:
declare @i INT
set @i=0
while @i<17
begin
set @i=@i+1
insert into stat2_1
select substring(word,@i,2),substring(word,@i+2,2),@i,count(*),0
from words
where len(word)>@i+3
group by substring(word,@i,2),substring(word,@i+2,2)
endСохраняю результат просто в текст, проверяю на данных – результат около 67%.
При этом нужно учитывать, что если слово не отсеивается как неправильное, то результат считается положительным. Это означает, что даже 67% достигается только благодаря тому, что примерно половина слов заведомо положительные, а это означает, что я отсеиваю чуть больше трети неправильных слов. Так как я перебрал практически все доступные варианты определения неправильности слова через комбинации букв прихожу к неутешительному выводу, что этот способ может работать только как дополнительный фильтр, и надо возвращаться к нейронным сетям. Ну не получится создать правила для опознания неправильных слов типа "numismatograph" и "troid".
Так как из-за слишком длительного обучения варианты с присутствием неправильных слов в наборе отпадают, решаю попробовать сеть Хопфилда. Нахожу готовую реализацию synaptic. Тестирую на небольшом наборе — результат на удивление неплохой. Проверяю массив на всех словах из 5 символов — результат превышает 80%. При этом библиотека даже умеет строить функцию, которая будет проверять данные без подключения самой библиотеки:
var run = function (input) {
F = {
0: 1,
1: 0,
...
370: -0.7308188776194796,
...
774: 8.232535948940295e-7
};
F[0] = input[0];
...
F[26] += F[0] * F[28];
F[26] += F[1] * F[29];
...
F[53] = (1 / (1 + Math.exp(-F[26])));
F[54] = F[53] * (1 - F[53]);
F[55] = F[56];
F[56] = F[57];
...
F[773] = (1 / (1 + Math.exp(-F[746])));
F[774] = F[773] * (1 - F[773]);
var output = [];
output[0] = F[53];
...
output[24] = F[773];
return output;
}Я наивно радуюсь (в очередной раз) и проверяю на всём массиве. Напомню, в прошлой части для обучения сетей я создал таблицу, в которой слова представлены последовательностью блоков по 5 бит, где каждый блок является двоичным представлением порядкового номера буквы в алфавите. Так как выгружаемые данные для 21*5 входных нейронов сильно превысят 64К, решаю разбивать длинные слова на две части и скармливать каждую из них.
Скрипт обучения:
var synaptic = require('synaptic');
var fs=require('fs');
var Neuron = synaptic.Neuron,
Layer = synaptic.Layer,
Network = synaptic.Network,
Trainer = synaptic.Trainer
function hopfield(size) {
var input = new synaptic.Layer(size);
var output = new synaptic.Layer(size);
this.set({
input: input,
hidden: [],
output: output
});
input.project(output, synaptic.Layer.connectionType.ALL_TO_ALL);
var trainer = new synaptic.Trainer(this);
this.learn = function(patterns) {
var set = [];
for (var p in patterns)
set.push({
input: patterns[p],
output: patterns[p]
});
return trainer.train(set, {
iterations: 50000,
error: .000000005,
rate: 1,
log:1
});
}
this.feed = function(pattern) {
var output = this.activate(pattern);
var pattern = [],
error = [];
for (var i in output) {
error[i] = output[i] > .5 ? 1 - output[i] : output[i];
pattern[i] = output[i] > .5 ? 1 : 0;
}
return {
pattern: pattern,
error: error
.reduce(function(a, b) {
return a + b;
})
};
}
}
hopfield.prototype = new synaptic.Network();
hopfield.prototype.constructor = hopfield;
var myPerceptron=new hopfield(11*5+2);
var array = fs.readFileSync('formining.csv').toString().split("n");
var trainingSet=[];
for(i in array) {
if (!(i%10000)) console.log(i);
var testdata=array[i].split(",");
var newtestdata1=[]
var newtestdata2=[]
var length = parseInt(testdata[0]?1:0);
//Первый символ в наборе данных означает длину
testdata.splice(0, 1);
//На всякий случай дополнительный бит, означающий начало слова
newtestdata1.push(0);
for(var j=0;j<11*5;j++){
newtestdata1.push(parseInt(testdata[j]?1:0)?1:0);
}
if(length>11)
{
//Дополнительный бит, означающий окончание первой части слова
newtestdata1.push(1);
//Значение "1" дополнительного бита, означающее начало второй части слова
newtestdata2.push(1);
for(var j=11*5;j<22*5;j++){
newtestdata2.push(parseInt(testdata[j]?1:0)?1:0);
}
//Значение "0" дополнительного бита, означающее окончание второй части слова
newtestdata2.push(0);
}
else {
//Значение "0" дополнительного бита, означающее окончание полного слова
newtestdata1.push(0);
}
trainingSet.push(newtestdata1);
if(length>11){
trainingSet.push(newtestdata2);
}
}
myPerceptron.learn(trainingSet);Цикл для получения результата такой же, только вместо trainingSet.push будет получение прогноза через myPerceptron.activate(newtestdataX) и побитовое сравнение с последним элементом строки со словом, в котором я сохранил результат (файл с данными, конечно же, будет тоже другим – с добавлением неправильных слов).
Проверяю.
Катастрофа.
Ни одного правильного ответа. Точнее, на все вопросы получаю положительный ответ. Возвращаюсь к набору из пяти символов. Работает нормально. Убираю вторую часть слова – всё равно не работает как надо. Путём экспериментов натыкаюсь на странную особенность: массив на пяти символах работает нормально ровно до тех пор, пока я его не перемешаю. То есть алгоритм хорошо обучился исключительно благодаря удачному расположению звёзд. В любой другой ситуации на большом объеме данных независимо от настроек данный конкретный алгоритм подбирает множители таким образом, что они дают положительный ответ практически при любом наборе данных.
В очередной раз расстраиваюсь. До конца конкурса остался всего день, но решаю продолжить поиски. Натыкаюсь на фильтр Блума. Ставлю заведомо большой размер (10000000). Проверяю. 95%. Ура! Уменьшаю до миллиона – результат ухудшается до 81%. Решаю заменить слова их хэшем:
function bitwise(str){
var hash = 0;
if (str.length == 0) return hash;
for (var i = 0; i < str.length; i++) {
var ch = str.charCodeAt(i);
hash = ((hash<<5)-hash) + ch;
hash = hash & hash; // Convert to 32bit integer
}
return hash;
}
function binaryTransfer(integer, binary) {
binary = binary || 62;
var stack = [];
var num;
var result = '';
var sign = integer < 0 ? '-' : '';
function table (num) {
var t = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
return t[num];
}
integer = Math.abs(integer);
while (integer >= binary) {
num = integer % binary;
integer = Math.floor(integer / binary);
stack.push(table(num));
}
if (integer > 0) {
stack.push(table(integer));
}
for (var i = stack.length - 1; i >= 0; i--) {
result += stack[i];
}
return sign + result;
}
function unique (text) {
var id = binaryTransfer(bitwise(text), 61);
return id.replace('-', 'Z');
}Результат стал 88%. Выгружаю данные – много. Думаю, как уменьшить. Уменьшаю размер фильтра до 500000 – результат ухудшается до 80%. Предполагаю, что надо уменьшить количество слов.
Логичный первый шаг – убрать более, чем 100K дублей слов с "'s". Но хотелось бы ещё что-нибудь более существенное сделать. Все опробованные варианты уменьшения словаря перечислять не буду, остановлюсь на последнем, который я выбрал в качестве рабочего:
Основная идея в том, чтобы убрать из словаря слова, которые уже содержатся в других словах, но с приставками и окончаниями, а к словам-поглотителям добавить битовую маску, которая будет говорить о том, есть ли правильные слова такие же, как это, но без первых/последних 1/2/3/4 букв. Потом в момент проверки будем брать слово и пробовать его со всеми возможными приставками и окончаниями.
Например (вариант с "'s"), слово "sucralfate's4" означает, что ещё существует слово "sucralfate", а слово "suckstone16" означает, что есть ещё и слово "stone", а "suctorian's12" означает, что и "suctorian", и "suctoria" тоже будут правильными.
Осталась самая малость – придумать, как создать такой справочник. В итоге получается такой алгоритм:
Делаем таблицы с приставками и окончаниями
select word,p=substring(word,len(word),1),w=substring(word,1,len(word)-1) into #a1 from words where len(word)>2
select word,p=substring(word,1,1),w=substring(word,2,len(word)-1) into #b1 from words where len(word)>2
select word,p=substring(word,len(word)-1,2),w=substring(word,1,len(word)-2) into #a2 from words where len(word)>3
select word,p=substring(word,len(word)-2,3),w=substring(word,1,len(word)-3) into #a3 from words where len(word)>4
select word,p=substring(word,len(word)-3,4),w=substring(word,1,len(word)-4) into #a4 from words where len(word)>5
select word,p=substring(word,1,2),w=substring(word,3,len(word)-2) into #b2 from words where len(word)>3
select word,p=substring(word,1,3),w=substring(word,4,len(word)-3) into #b3 from words where len(word)>3
select word,p=substring(word,1,4),w=substring(word,5,len(word)-4) into #b4 from words where len(word)>4Общая таблица для результата
select word,
substring(word,len(word),1) s1, substring(word,1,len(word)-1) sw1,
substring(word,len(word)-1,2) s2, substring(word,1,len(word)-2) sw2,
substring(word,len(word)-2,3) s3, substring(word,1,len(word)-3) sw3,
IIF(len(word)>4,substring(word,len(word)-3,4),'') s4, IIF(len(word)>4,substring(word,1,len(word)-4),'') sw4,
substring(word,1,1) p1,substring(word,2,len(word)-1) pw1,
substring(word,1,2) p2,substring(word,3,len(word)-2) pw2,
substring(word,1,3) p3,substring(word,4,len(word)-3) pw3,
IIF(len(word)>4,substring(word,1,4),'') p4,IIF(len(word)>4,substring(word,5,len(word)-4),'') pw4,
se1=null,se2=null,se3=null,se4=null,pe1=null,pe2=null,pe3=null,pe4=null,excluded=0
into #tmpwords from words where len(word)>2Индексы, чтобы не ждать вечность
create index a1 on #tmpwords(word)
create index p0 on #tmpwords(s1)
create index p1 on #tmpwords(sw1)
create index p2 on #tmpwords(s2)
create index p3 on #tmpwords(sw2)
create index p4 on #tmpwords(s3)
create index p5 on #tmpwords(sw3)
create index p6 on #tmpwords(s4)
create index p7 on #tmpwords(sw4)
create index p20 on #tmpwords(p1)
create index p30 on #tmpwords(pw1)
create index p21 on #tmpwords(p2)
create index p31 on #tmpwords(pw2)
create index p41 on #tmpwords(p3)
create index p51 on #tmpwords(pw3)
create index p61 on #tmpwords(p4)
create index p71 on #tmpwords(pw4)Считаем и сохраняем количество слов с каждой приставкой и окончанием каждой длины:
select p into #a11 from #a1 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #a21 from #a2 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #a31 from #a3 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #a41 from #a4 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b11 from #b1 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b21 from #b2 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b31 from #b3 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b41 from #b4 a join words w on w.word=a.w and len(w.word)>2
group by p
having count(*)>1Помечаем слова-поглотители в таблице с результатом
update w set se1=1 from #tmpwords w join #a11 a on a.p=w.s1 join #tmpwords t on t.word=w.sw1
update w set se2=1 from #tmpwords w join #a21 a on a.p=w.s2 join #tmpwords t on t.word=w.sw2
update w set se3=1 from #tmpwords w join #a31 a on a.p=w.s3 join #tmpwords t on t.word=w.sw3
update w set se4=1 from #tmpwords w join #a41 a on a.p=w.s4 join #tmpwords t on t.word=w.sw4
update w set pe1=1 from #tmpwords w join #b11 a on a.p=w.p1 join #tmpwords t on t.word=w.pw1
update w set pe2=1 from #tmpwords w join #b21 a on a.p=w.p2 join #tmpwords t on t.word=w.pw2
update w set pe3=1 from #tmpwords w join #b31 a on a.p=w.p3 join #tmpwords t on t.word=w.pw3
update w set pe4=1 from #tmpwords w join #b41 a on a.p=w.p4 join #tmpwords t on t.word=w.pw4Создаём объединённый результат для того, чтобы выбрать наиболее частые варианты
select s1 p,count(*) cnt into #suffixes from #tmpwords where se1 is not NULL group by s1
union all
select s2,count(*) from #tmpwords where se2 is not NULL group by s2
union all
select s3,count(*) from #tmpwords where se3 is not NULL group by s3
union all
select s4,count(*) from #tmpwords where se4 is not NULL group by s4
select p1,count(*) cnt into #prefixes from #tmpwords where pe1 is not NULL group by p1
union all
select p2,count(*) from #tmpwords where pe2 is not NULL group by p2
union all
select p3,count(*) from #tmpwords where pe3 is not NULL group by p3
union all
select p4,count(*) from #tmpwords where pe4 is not NULL group by p4Оставляем только те, которые встречаются больше, чем в 100 словах.
select *,'s' type ,IIF(cnt>100,0,1) excluded into #result from #suffixes
union all
select *,'p' type, IIF(cnt>100,0,1) excluded from #prefixesОбнуляем статистику
update #tmpwords set se1=null,se2=null,se3=null,se4=null,pe1=null,pe2=null,pe3=null,pe4=nullУдаляем "лишние" приставки и окончания
delete a from #a11 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete a from #a21 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete a from #a31 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete a from #a41 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete a from #b11 a join #result r on r.p=a.p and r.type='p' and excluded=1
delete a from #b21 a join #result r on r.p=a.p and r.type='p' and excluded=1
delete a from #b31 a join #result r on r.p=a.p and r.type='p' and excluded=1
delete a from #b41 a join #result r on r.p=a.p and r.type='p' and excluded=1
Обновляем статистику для оставшихся наиболее часто встречаемых.
update w set se1=1 from #tmpwords w join #a11 a on a.p=w.s1 join #tmpwords t on t.word=w.sw1
update w set se2=1 from #tmpwords w join #a21 a on a.p=w.s2 join #tmpwords t on t.word=w.sw2
update w set se3=1 from #tmpwords w join #a31 a on a.p=w.s3 join #tmpwords t on t.word=w.sw3
update w set se4=1 from #tmpwords w join #a41 a on a.p=w.s4 join #tmpwords t on t.word=w.sw4
update w set pe1=1 from #tmpwords w join #b11 a on a.p=w.p1 join #tmpwords t on t.word=w.pw1
update w set pe2=1 from #tmpwords w join #b21 a on a.p=w.p2 join #tmpwords t on t.word=w.pw2
update w set pe3=1 from #tmpwords w join #b31 a on a.p=w.p3 join #tmpwords t on t.word=w.pw3
update w set pe4=1 from #tmpwords w join #b41 a on a.p=w.p4 join #tmpwords t on t.word=w.pw4Помечаем "поглощённые" слова
update t set excluded=1 from #tmpwords w join #a11 a on a.p=w.s1 join #tmpwords t on t.word=w.sw1
update t set excluded=1 from #tmpwords w join #a11 a on a.p=w.s1 join #tmpwords t on t.word=w.sw1
update t set excluded=1 from #tmpwords w join #a21 a on a.p=w.s2 join #tmpwords t on t.word=w.sw2
update t set excluded=1 from #tmpwords w join #a31 a on a.p=w.s3 join #tmpwords t on t.word=w.sw3
update t set excluded=1 from #tmpwords w join #a41 a on a.p=w.s4 join #tmpwords t on t.word=w.sw4
update t set excluded=1 from #tmpwords w join #b21 a on a.p=w.p2 join #tmpwords t on t.word=w.pw2
update t set excluded=1 from #tmpwords w join #b31 a on a.p=w.p3 join #tmpwords t on t.word=w.pw3
update t set excluded=1 from #tmpwords w join #b41 a on a.p=w.p4 join #tmpwords t on t.word=w.pw4
Профит :-)
select excluded,count(*) cnt from #tmpwords group by excluded| excluded | cnt |
|---|---|
| 0 | 397596 |
| 1 | 232505 |
Справочник сжался на 232505 записей "без потерь".
Теперь надо сделать проверку. Она сильно усложнилась и замедлилась из-за необходимости перебора всех возможных приставок и окончаний:
//Проверяем слово без изменений
result=bloom.test(unique(word))
if(result){
return true;
}
//Потом начинаем искать его модификации
for(var i=0;i<255;i++)
{
//Если слово само является словом-поглотителем
result=bloom.test(unique(word+i))
if(result){
return true;
}
//Проверяем с приставками и окончаниями
for (var part in parts ){
//1-окончание,2-приставка
var testword=(parts[part]==2?part:"")+word+(parts[part]==1?part:"");
//Количество символов является степенью двойки в битовой маске, приставки смещены на 4 бита
bitmask=Math.pow(2,(parts[part]-1)*4+part.length);
//Проверяем только допустимые варианты
if(i&bitmask==bitmask){
result=bloom.test(unique(testword+i))
if (result){
return true
}
}
}Запускаю. Результат ухудшился. Но ведь он должен был улучшиться! Времени не остаётся, отладчик в вебсторме жутко глючит, разобраться уже не успеваю. Отправлять то, что есть, смысла нет, но было интересно. Надеюсь, и вам тоже. "Отпуск" заканчивается, пора возвращаться к своим баранам своему проекту. Спасибо за внимание.
Автор:
