Відпустку программистски, або як я не взяв участь у конкурсі з програмування на PHP. Частина друга

першої частини цього опису спроби вирішення цікавою конкурсною завдання я розповів про підготовку даних для аналізу і про кількох експериментах. Нагадаю, умова завдання полягало в тому, щоб з найбільшою ймовірністю визначити наявність слова у словнику, не маючи доступу до цього словника у момент виконання програми з обмеженням на обсяг програми (включаючи дані) у 64K.
image
Як і минулого разу, під катом багато SQL, JS, а також нейронні мережі і фільтр Блума.
Нагадаю, останнім описаним експериментом була спроба вирішити задачу через побудову дерева прийняття рішення. Наступного перевіряється технологією був алгоритм пошуку взаємозв'язків, що входить в пакет Microsoft Data Mining. Ось так виглядає результат його роботи:
image
На картинці видно, що алгоритм нам показує, що, на його думку, якщо в слові 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 words from where charindex("",word)>0
union
select length=len(word),'a' letter, charindex('a',word) number words from where charindex('a',word)>0
...
union
select length=len(word),'z' letter, charindex('z',word) number words from where charindex('z',word)>0

Робимо декартів добуток букв, довжин і позицій, а потім left join на існуючі
select l.length,a.letter,l.length from allchars a
cross join (select number 1 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),int pos,cright int,cwrong int)
create table stat3(letters char(3),int pos,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 @INT i
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 @INT i
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).
Роблю зведену таблицю. Результат виглядає так:
image
Роблю дані для програми: пара + бітова маска (див. формулу вгорі картинки).
image
Код завантаження аналогічний описаному в першій частині, а от перевірка змінюється.
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%. Виникає бажання трохи "схитрувати" і поліпшити результат, спираючись на логіку роботи генератора:
  1. Вважати всі повтори правильними словами, т. к. неправильні повторюються набагато рідше. Є якісь дивні явні лідери по повторам серед неправильних, але їх можна просто описати як виключення.
  2. Стежити за пропорціями правильно/неправильно в пакетах з 100 слів і вирівнювати їх після перекосу 60/40.
Але обидва цих варіанти a) ненадійні і б) "неспортивні", тому залишаю на потім.
Хочу зробити останню перевірку без обмеження на обсяг даних, щоб переконатися в тому, що "описовим" способом вирішити задачу неможливо. Для цього вирішую до перевірок додати всі "сусідять" пари і трійки символів. Починаю з пар, наповнюю таблицю:
declare @INT i
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.232535948940295 e-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 integer 32bit
}
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 words from where len(word)>2
select word,p=substring(word,1,1),w=substring(word,2,len(word)-1) into #b1 words from where len(word)>2
select word,p=substring(word,len(word)-1,2),w=substring(word,1,len(word)-2) into #a2 words from where len(word)>3
select word,p=substring(word,len(word)-2,3),w=substring(word,1,len(word)-3) into #a3 words from where len(word)>4
select word,p=substring(word,len(word)-3,4),w=substring(word,1,len(word)-4) into #a4 words from where len(word)>5
select word,p=substring(word,1,2),w=substring(word,3,len(word)-2) into #b2 words from where len(word)>3
select word,p=substring(word,1,3),w=substring(word,4,len(word)-3) into #b3 words from where len(word)>3
select word,p=substring(word,1,4),w=substring(word,5,len(word)-4) into #b4 words from 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 words from 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 on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #a21 from #a2 a join words on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #a31 from #a3 a join words on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #a41 from #a4 a join words on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b11 from #b1 a join words on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b21 from #b2 a join words on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b31 from #b3 a join words on w w.word=a.w and len(w.word)>2
group by p
having count(*)>1
select p into #b41 from #b4 a join words on w 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 from a #a11 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete from a #a21 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete from a #a31 a join #result r on r.p=a.p and r.type='s' and excluded=1
delete from a #a41 a join #result r on r.p=a.p and r.type='s' and excluded=1

delete from a #b11 a join #result r on r.p=a.p and r.type='p' and excluded=1
delete from a #b21 a join #result r on r.p=a.p and r.type='p' and excluded=1
delete from a #b31 a join #result r on r.p=a.p and r.type='p' and excluded=1
delete from a #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
}
}
}

Запускаю. Результат погіршився. Але ж він повинен був покращитися! Часу не залишається, відладчик в вебсторме страшно глючить, розібратися вже не встигаю. Відправляти те, що є, немає сенсу, але було цікаво. Сподіваюся, і вам теж. "Відпустка" закінчується, пора повертатися до своїм баранів своєму проекту. Дякую за увагу.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.