В первой части этого описания попытки решения интересной конкурсной задачи я рассказал о подготовке данных для анализа и о нескольких экспериментах. Напомню, условие задачи заключалось в том, чтобы с наибольшей вероятностью определить наличие слова в словаре, не имея доступа к этому словарю в момент выполнения программы и с ограничением на объем программы (включая данные) в 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

Действительно, разница больше, чем в 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%. Возникает желание немного "схитрить" и улучшить результат, опираясь на логику работы генератора:

1. Считать все повторы правильными словами, т.к. неправильные повторяются намного реже. Есть какие-то странные явные лидеры по повторам среди неправильных, но их можно просто описать как исключения.
2. Следить за пропорциями правильно/неправильно в пакетах из 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

Справочник сжался на 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
            }
        }
}

Запускаю. Результат ухудшился. Но ведь он должен был улучшиться! Времени не остаётся, отладчик в вебсторме жутко глючит, разобраться уже не успеваю. Отправлять то, что есть, смысла нет, но было интересно. Надеюсь, и вам тоже. "Отпуск" заканчивается, пора возвращаться к своим баранам своему проекту. Спасибо за внимание.