| | /*
=== НАСТРОЙКИ ========================================================================
Добавляем в словарь так:
названия Название-с-символами,samsung, nokia .
Добавляем возможные опечатки так:
опечатки a -> o, u -> a, 0123 -> 4567, аб -> цд .
Можно сделать тест быстродействия так:
использовать алфавит абвгдеёжзийклмнопрстуфхцчшщъыьэюя.
добавить 1000 брендов по 3 символа с 0 ошибок.
=== ФАЙЛ РАЗБОРА =====================================================================
названия "Метро",Домик-в-деревне,samsung,sunsung,nokia,microsoft,1984.
опечатки
abcdefghijklmnopqrstuvwxyz ->
abcdefghijklmnopqrstuvwxyz,
абвгдеёжзийклмнопрстуфхцчшщъыьэюя ->
абвгдеёжзийклмнопрстуфхцчшщъыьэюя,
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ ->
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ,
012345689 -> 012345689.
"Митра" Бобик-в-деревне Домик-в-деревне
sunsung samsung sumsung samsyng sumsyng sumcung
nakia nakua macrosoft microsoft 1945
=== СИНТЕТИЧЕСКИЙ ТЕСТ БЫСТРОДЕЙСТВИЯ ================================================
опечатки
abcdefghijklmnopqrstuvwxyz ->
abcdefghijklmnopqrstuvwxyz,
абвгдеёжзийклмнопрстуфхцчшщъыьэюя ->
абвгдеёжзийклмнопрстуфхцчшщъыьэюя,
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ ->
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ,
012345689 -> 012345689.
использовать алфавит абвгдеёжзийклмнопрстуфхцчшщъыьэюя.
проверять 2 опечатки.
возвращать все варианты.
добавить 100000 брендов по 3 символа.
добавить 100000 брендов по 4 символа.
добавить 100000 брендов по 5 символа.
добавить 100000 брендов по 6 символа.
добавить 100000 брендов по 7 символа.
добавить 100000 брендов по 8 символа.
===================== ОПЕЧАТОК 2, БРЕНДОВ 5981, ВСЕ ВАРИАНТЫ =========================
длинаСлова | 8| 7| 6| 5| 4| 3
провереноСлов | 1000| 1000| 1000| 1000| 1000| 983
найденоВариантов | 1116| 1083| 1095| 1486| 8541| 106542
затрачено | 24.89| 18.26| 11.99| 3.73| 2.14| 0.98
словВСекунду | 40.17| 54.78| 83.42| 268.24| 467.29| 1004.09
словВМинуту | 2410.41| 3286.77| 5005.42| 16094.42| 28037.38| 60245.15
ожидаюТысячуСловЗа | 00:24.89| 00:18.26| 00:11.99| 00:3.73| 00:2.14| 00:01
===================== ОПЕЧАТОК 2, БРЕНДОВ 5973, ПЕРВЫЙ ВАРИАНТ =======================
длинаСлова | 8| 7| 6| 5| 4| 3
провереноСлов | 1000| 1000| 1000| 1000| 999| 978
найденоВариантов | 1000| 1000| 1000| 1000| 999| 978
затрачено | 13.12| 9.2| 5.91| 1.58| 0.3| 0.02
словВСекунду | 76.21| 108.73| 169.26| 634.92| 3318.94| 51473.68
словВМинуту | 4572.47| 6523.87| 10155.72| 38095.24| 199136.21|3088421.05
ожидаюТысячуСловЗа | 00:13.12| 00:9.2| 00:5.91| 00:1.58| 00:0.3| 00:0.02
===================== ОПЕЧАТОК 2, БРЕНДОВ 524203, ВСЕ ВАРИАНТЫ =======================
длинаСлова | 8| 7| 6| 5| 4| 3
провереноСлов | 1000| 1000| 1000| 1000| 1000| 1000
найденоВариантов | 4669| 3133| 3101| 41951| 687313| 3010378
затрачено | 29.84| 21.55| 13.03| 5.3| 3.49| 2.26
словВСекунду | 33.51| 46.4| 76.75| 188.79| 286.78| 442.09
словВМинуту | 2010.66| 2783.71| 4605.11| 11327.17| 17206.77| 26525.2
ожидаюТысячуСловЗа | 00:29.84| 00:21.55| 00:13.03| 00:5.3| 00:3.49| 00:2.26
===================== ОПЕЧАТОК 2, БРЕНДОВ 524263, ПЕРВЫЙ ВАРИАНТ =====================
длинаСлова | 8| 7| 6| 5| 4| 3
провереноСлов | 1000| 1000| 1000| 1000| 1000| 1000
найденоВариантов | 1000| 1000| 1000| 1000| 1000| 1000
затрачено | 7.04| 6.82| 3.22| 0.37| 0.22| 0
словВСекунду | 142.13| 146.61| 310.95| 2688.17| 4524.89| 250000
словВМинуту | 8527.57| 8796.36| 18656.72| 161290.32| 271493.21| 15000000
ожидаюТысячуСловЗа | 00:7.04| 00:6.82| 00:3.22| 00:0.37| 00:0.22| 00:00
*/
{
if (!options.бренды) { options.бренды = {}; }
if (!options.опечатки) { options.опечатки = {}; }
options.статистика = [];
options.time = ()=>window.performance.now()
options.lastTime = 0;
options.maxTypos = 2;
options.allVariants = true;
options.alphabet = 'abcdefghijklmnopqrstuvwxyz';
options.random =(length) => Math.floor(length * Math.random()) % length;
options.randomAlpha = ()=> options.alphabet[options.random(options.alphabet.length)];
options.checkBrands = (бренды, сОпечатками)=>{
бренды.forEach(_=>{
var nw = [..._];
var i = options.random(nw.length);
var j = options.random(nw.length);
j = j == i ? (i + 1 < nw.length ? i + 1 : i - 1) : j;
if (сОпечатками>=1) {
nw[i] = options.randomAlpha();
}
if (сОпечатками>=2) {
nw[j] = options.randomAlpha();
}
for(var i = 0; i < 1; ++i){
let время3 = options.time();
let ctx = {варианты:[]};
if (options.word(ctx,nw,options.maxTypos)) {
options.addStat(ctx, время3);
} else {
console.log(`${_.join('')} != ${nw.join('')}`)
}
}
})
}
options.addBrands = (количество, длина, сОпечатками)=>{
var все = [];
var строки = {};
for(var и = 0; и < количество; ++и) {
var бренд = (()=>{
var попыток = 0;
do {
var слово = [...Array(длина).keys()].map(_=>options.randomAlpha());
} while(строки[слово] && попыток++ < 10);
return слово;
})();
var строка = бренд.join('');
options.addBrand(строка);
if (все.length < 1000 && !строки[строка]) {
строки[строка] = true;
все.push(бренд);
}
}
options.checkBrands(все, сОпечатками);
}
options.addStat = (ctx,time)=>{
var время = options.time();
var затрачено = время - (options.lastTime? options.lastTime: time);
options.lastTime = время;
var длинаСлова = ctx.варианты[0].правильно.length;
var стат = options.статистика[длинаСлова];
if (!стат) { стат = options.статистика[длинаСлова] =
{провереноСлов:0,найденоВариантов:0,длинаСлов:0,затрачено:0};}
стат.длинаСлов += длинаСлова;
++стат.провереноСлов;
стат.найденоВариантов += ctx.варианты.length;
стат.затрачено += затрачено;
return ctx;
}
options.endStat = (статистика)=>{
var всё = статистика;
console.log(статистика)
всё.forEach(стат=>{
стат.длинаСлова = стат.длинаСлов / стат.провереноСлов;
стат.затрачено /= 1000;
стат.словВСекунду = стат.провереноСлов / стат.затрачено;
стат.словВМинуту = 60 * стат.словВСекунду;
стат.ожидаюТысячуСловЗа = options.formatMinutesToTime(options.round(1000 / стат.словВСекунду));
});
return статистика;
}
options.round = (value)=>{
if (typeof value == "string"){return value;}
return Math.round(value*100)/100;
}
options.summary = (stat) => {
const отфильтрованный = stat.filter(Boolean);
// Сортируем по убыванию длины слова (больше вначале)
отфильтрованный.sort((a, b) => b.длинаСлова - a.длинаСлова);
const ключи = [
'длинаСлова','провереноСлов','найденоВариантов',
'затрачено','словВСекунду','словВМинуту',
'ожидаюТысячуСловЗа'
];
// Формируем строки отчёта за один проход
const строки = ключи.map(поле => {
const значения = отфильтрованный.map(стат => String(options.round(стат[поле])).padStart(10, ' ')).join('|');
return поле.padEnd(20, ' ') + '|' + значения;
});
строки.unshift(
`===================== ОПЕЧАТОК ${options.maxTypos}, БРЕНДОВ ${Object.keys(options.бренды).length}, ${options.allVariants?'ВСЕ ВАРИАНТЫ':'ПЕРВЫЙ ВАРИАНТ'} `.
padEnd(строки[0].length,'='));
const отчёт = строки.join('\n');
console.log(отчёт);
return отчёт;
}
options.addHash = (dictionary, text)=>{
let hash = dictionary[options.hash(text)];
if (!hash) {
hash = dictionary[options.hash(text)] = {коллизии:0};
}
if (options.коллизии) {
if (hash.коллизии >= 2) {
if (!hash.варианты){ hash.варианты = {}; }
hash.варианты[text.join('')] = true;
}
} else {
++hash.коллизии;
}
}
options.add = (dictionary, from, to)=>{
var obj = dictionary;
[from,to,'.'].forEach(_=>{
var next = obj[_];
obj = next = next?next:(obj[_]={});
});
}
options.addBrand = (name)=> options.addHash(options.бренды, name);
options.addTypo = (from,to)=>
from.forEach(f=>to.forEach(t=>
f != t ? options.add(options.опечатки, f,t) : null
));
options.hash = (string) => {
let hash = 0;
for (const char of string) {
hash = (hash << 5) - hash + char.charCodeAt(0);
hash |= 0; // Constrain to 32bit integer
}
return hash;
};
options.valid = (ctx,word)=>{
var коллизии = options.бренды[options.hash(word)];
if (коллизии && коллизии.коллизии > 1) {
return !!коллизии.варианты[word.join('')];
}
return !!коллизии;
}
options.word = (ctx, word, maxTypos) => {
let успешно = false;
const addVariant = (typos, nw) => {
ctx.варианты.push({
опечаток: typos,
правильно: nw.join(''),
оригинал: word.join('')
});
};
if (options.valid(ctx, word)) {
addVariant(0, word);
if (maxTypos === 0 || !options.allVariants) return true;
успешно = true;
}
if (maxTypos < 1) return успешно;
const chars = word;
const len = chars.length;
const generateTypos = (positions, typosLeft, nw, start) => {
if (typosLeft === 0) {
if (options.valid(ctx, nw)) {
addVariant(positions.length, nw);
if (!options.allVariants) return true;
успешно = true;
}
return;
}
for (let i = start; i < len; i++) {
if (positions.includes(i)) continue;
const список = options.опечатки[chars[i]];
if (!список) continue;
for (const оп of Object.keys(список)) {
const newWord = nw.slice();
newWord[i] = оп;
if (generateTypos([...positions, i], typosLeft - 1, newWord, i + 1)){
return true;
}
}
}
};
for (let typosCount = 1; typosCount <= maxTypos && typosCount <= 2; typosCount++) {
if (generateTypos([], typosCount, chars, 0)) {
return true;
}
}
return успешно;
}
options.formatMinutesToTime = (totalMinutes)=> {
const hours = Math.floor(totalMinutes / 60);
const minutes = totalMinutes % 60;
const formattedHours = String(hours).padStart(2, '0');
const formattedMinutes = String(minutes).padStart(2, '0');
return `${formattedHours}:${formattedMinutes}`;
}
}
words = _ dtime:time description (_ (addBrands/useAlphabet/checkTypos/returnVariants))*
&{console.log('brands', options.бренды); return true;}
_ time:time ws:(w:word _ {return w;})*
{
var времяНастройки = options.formatMinutesToTime((time-dtime) / 1000);
var времяРазбора = options.formatMinutesToTime((options.time()-time) / 1000);
return {
результат:ws,
времяНастройки,
времяРазбора,
статистика:options.summary(options.endStat(options.статистика))};
}
ctx = &(.) {return {варианты:[]};}
skipword = ctx:ctx word:alphabet+
&{return options.word(ctx,word,options.maxTypos);} { return ctx;}
word = time:time ctx:ctx word:alphabet+
&{return options.word(ctx,word,options.maxTypos);}
{ return options.addStat(ctx,time);}
_ = [ \t\r\n]*
alphabet = s:[0123456789a-zA-Zа-яА-ЯёЁ\!\-\+\*\"\'] {return s;}
string = s:alphabet+ {return s;}
letter = s:alphabet+ {return s;}
brand = s:string{return s;}
addBrand =
"названия" _ (s:brand { options.addBrand(s); return null;})
("," _ s:brand { options.addBrand(s); return null;})* _ "." {return null;}
addTypo =
"опечатки" _
(from:letter _ "->" _ to:letter
{ options.addTypo(from,to); return null;})
("," _ from:letter _ "->" _ to:letter
{ options.addTypo(from,to); return null;})* _
"." {return null}
predescription = desc:((addBrand / addTypo) _)+ {return desc}
description = &predescription
&{ return options.коллизии = true;}
desc:predescription {return desc}
time = &{return true;} { return options.time(); }
integer = i:[0123456789]+ {return +i.join('');}
addBrands = "добавить" _ count:integer _ ("брендов"/"бренд") _
"по" _ length:integer _ ("символа"/"символов") _ "."
{options.addBrands(count,length,options.maxTypos); return true;}
useAlphabet = "использовать" _ "алфавит" _ alpha:alphabet+ _ "."
{ options.alphabet = alpha; return alpha;}
checkTypos = "проверять" _ count:integer _
("опечаток"/"опечатки"/"опечатку") _ "."
{ options.maxTypos = count; return count;}
returnVariants = "возвращать" _
all:("все" _ "варианты" {return true;} /
"первый" _ "вариант" {return false;})
_ "."
{ options.allVariants = all; return all;}
|
