Похожесть двух строк
Здравствуйте.
Есть паттерны: 1. Есть ли в наличии ([\s\S]+)? 2. Есть ли ([\s\S]+) в наличии? Есть строка: Если ли в наличии лопата? В строке допущена опечатка, вместо "есть" написано "если". Нужно как-то определить, что полученная строка удовлетворяет шаблону 1 с небольшими корректировками. Хотел воспользоваться расстоянием Левенштейна, однако не выходит, т.к. строка сравнивается с паттерном. Можно как-нибудь решить эту проблему без машинного обучения? |
Цитата:
var re=/Ес\S\S ли в наличии ([\s\S]+)\?/; var str='Есть ли в наличии булки?'; alert(str+' - '+re.test(str)); str='Если ли в наличии цветы?'; alert(str+' - '+re.test(str)); |
ksa, чтобы применить это на практике, нужно точно знать какие символы пользователь "перепутал". В противном случае от статичного текста придется полностью отказаться в угоду выражений, что позволит ввести любое предложение, главное, чтобы введенные символы стояли на своих местах.
Нужно будет проверить кол-во ложных срабатываний этого подхода. |
Цитата:
Я лишь ответил на твой... :) |
condator, случай реальный.
|
Трэд ниасилил, только название, но посоветую
https://ru.wikipedia.org/wiki/Расстояние_Левенштейна https://www.npmjs.com/package/fast-levenshtein |
ДЖАВАСКРИПТИЗЕР, пост ради поста?
Цитата:
|
нет, просто я немного ленив
Почему не выходит леванштейн. Вот у тебя есть запрос: "есть ли в наличии глюкало?" 1) Матчем выдираешь слово глюкало 2) Бежишь по списку товаров (ты ведь знаешь названия товаров которые у тебя есть) и считаешь леванштейны 3) дальше все и так понятно В машинное обучение можно смотреть если уже есть опыт иначе это грозит потерей уймы времени с нулевым результатом в итоге |
Цитата:
Цитата:
Цитата:
|
Можно попробовать логировать запросы. Через некоторе время соберется статистика по наиболее частым и типичным опечаткам. Дальше можно составить набор правил по которым попытаться исправить ошибки. И матчить уже исправленную строку.
Например у нас есть куча таких запросов: Как снять двушку? 1) Для начала нормализуем строку удалив все двойные пробелы 2) Слово "двушку" смело меняем на "девушку" ибо ни кто в здравом уме двушки в 11 вечера не снимает 3) Пытаемся подобрать паттерн Пример шуточный. Наиболее частые ошибки можно пытаться исправлять, на остальные забить метиз с метрической резьбой. |
ДЖАВАСКРИПТИЗЕР,
Цитата:
<iframe width="560" height="315" src="https://www.youtube.com/embed/tWEBbYoDaU8?start=25" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen style="margin: auto;"></iframe>На все ваши возражения смотрите 1:03 там же! Nexus, Пусть имеются строки a и b, задача заключается в том, чтобы найти такую функцию F(x), чтобы для похожих в некотором смысле строк выполнялось F(a) === F(b) Первым приближением F(x) может быть перевод в нижний регистр. Действительно, F("Есть ли") === F("есть ли") Вторым приближением может быть добавленная транслитерация, F("Есть ли") === F("еst li") или F("Ест ли") === F("есть ли") Третим приближением может быть добавленный алгоритм сравнения двух строк по их звучанию (например, SOUNDEX (произносится как /ˈsaʊndɛks/ или /ˈsaʊɾ̃ɛks/), но для русского языка лучше подходит «Полифон»[1]), F("Ест ли") === F("есть ли") или F("Если ли") === F("есть ли") Конечно, простое регулярное выражение не подойдёт для определения, подходит ли строка под РегВыр, для этого его нужно трансформировать по определённым правилам, но можно обойтись обёрткой над простыми РегВырами. (я назвал её Rx) Алгоритм ставит определённому сочетанию букв одинаковый код, если они звучат одинаково. Рассмотрите пример. Слово «сердце» произносится как /ˈs̪ʲɛ̝rt̻͡s̪ɨ̞/, из-за этого оно может писаться с ошибкой, писаться так, как оно звучит — «серце», или «сертце». Рассматривая /rt̻͡s̪/, становится понятно, что этой группе согласных может соответствовать «рдц», «рц» или «ртц». Согласные заменяются на числа, причём похожим по звучанию буквам/группам букв соответствуют одинаковые числа. Проверить подходить ли предложение под Rx регулярное выражение можно так
const ok = Rx`Есть ли ${/.+/} в наличии?`.test("Если ли лапата в налеции?");
Если же нужно именно слово, которое совпало в захватывающей группе, то его напрямую получить нельзя. (И действительно, если вы получите из этого предложения «лапата», то что с этим делать дальше? Вместо этого, предлагается код этого слова 873. У вас в базе данных может храниться слово «лопата», вычислив Soundex("лопата") получите 873, сравнив узнаете, что «лапата» оказывается — «лопата»)
const match = Rx`Есть ли ${/.+/} в наличии?`.match("Если ли лапата в налеции?");
В предложенном варианте Soundex это не SOUNDEX, а приспособленное к русскому языку поделие, основанное на алгоритмах SOUNDEX и «Полифон», нуждается в некоторой доработке в плане данных объекта Soundex.prototype._codes Итоговый пример, в котором вы можете ввести предложение, и программа проверит под какое Rx регулярное выражение подходит предложение (походящее выделится зелёным цветом!) Продолжение следует... |
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<style>
#inputField {
font-size: 200%;
width: 100%;
box-sizing: border-box;
}
#patternsField > * {
border: 1px solid #eee;
border-radius: .4em;
margin: 1em 0;
padding: 1em;
font: bold 1em sans-serif;
}
#patternsField > .matches {
background-color: #4CAF50;
color: white;
}
</style>
</head>
<body>
<input id="inputField" value="Если ли в нолечие лапата?">
<div id="patternsField"></div>
<script>
function Soundex(expression) {
if(this instanceof Soundex === false)
return new Soundex(expression);
this.expression = expression;
this.calculate(this.expression);
}
Soundex.prototype = {
__proto__: Array.prototype,
_codes: {
"a":{
"0":[0,-1,-1],
"i":[[0,1,-1]],
"j":[[0,1,-1]],
"y":[[0,1,-1]],
"u":[[0,7,-1]]
},
"b":[[7,7,7]],
"c":{
"0":[5,5,5],
"1":[4,4,4],
"z":{"0":[4,4,4],"s":[[4,4,4]]},
"s":{"0":[4,4,4],"z":[[4,4,4]]},
"k":[[5,5,5],[45,45,45]],
"h":{"0":[5,5,5],"1":[4,4,4],"s":[[5,54,54]]}
},
"d":{
"0":[3,3,3],
"t":[[3,3,3]],
"z":{"0":[4,4,4],"h":[[4,4,4]],"s":[[4,4,4]]},
"s":{"0":[4,4,4],"h":[[4,4,4]],"z":[[4,4,4]]},
"r":{"s":[[4,4,4]],"z":[[4,4,4]]}
},
"e":{
"0":[0,-1,-1],
"i":[[0,1,-1]],
"j":[[0,1,-1]],
"y":[[0,1,-1]],
"u":[[1,1,-1]],
"w":[[1,1,-1]]
},
"f":{"0":[7,7,7],"b":[[7,7,7]]},
"g":[[5,5,5]],
"h":[[5,5,-1]],
"i":{
"0":[0,-1,-1],
"a":[[1,-1,-1]],
"e":[[1,-1,-1]],
"o":[[1,-1,-1]],
"u":[[1,-1,-1]]
},
"j":[[4,4,4]],
"k":{"0":[5,5,5],"h":[[5,5,5]],"s":[[5,54,54]]},
"l":[[8,8,8]],
"m":{"0":[6,6,6],"n":[[66,66,66]]},
"n":{"0":[6,6,6],"m":[[66,66,66]]},
"o":{"0":[0,-1,-1],"i":[[0,1,-1]],"j":[[0,1,-1]],"y":[[0,1,-1]]},
"p":{"0":[7,7,7],"f":[[7,7,7]],"h":[[7,7,7]]},
"q":[[5,5,5]],
"r":{
"0":[9,9,9],
"d": {"0":[93,93,93],"c":[[95,95,95]]},
"t": {"0":[93,93,93],"c":[[95,95,95]]},
"z":[[94,94,94],[94,94,94]],
"s":[[94,94,94],[94,94,94]]
},
"s":{
"0":[4,4,4],
"l":{"0":[2,43,43]},
"z":{
"0":[4,4,4],
"t":[[2,43,43]],
"c":{"z":[[2,4,4]],"s":[[2,4,4]]},
"d":[[2,43,43]]
},
"d":[[2,43,43]],
"t":{
"0":[2,43,43],
"r":{"z":[[2,4,4]],"s":[[2,4,4]]},
"n":[[26,46,46]],
"c":{"h":[[2,4,4]]},
"s":{"h":[[2,4,4]],"c":{"h":[[2,4,4]]}}
},
"c":{
"0":[2,4,4],
"h":{
"0":[4,4,4],
"t":{
"0":[2,43,43],
"s":{"c":{"h":[[2,4,4]]},"h":[[2,4,4]]},
"c":{"h":[[2,4,4]]}
},
"d":[[2,43,43]]
}
},
"h":{
"0":[4,4,4],
"t":{"0":[2,43,43],"c":{"h":[[2,4,4]]},"s":{"h":[[2,4,4]]}},
"c":{"h":[[2,4,4]]},
"d":[[2,43,43]]
}
},
"t":{
"0":[3,3,3],
"c":{"0":[4,4,4],"h":[[4,4,4]]},
"z":{"0":[4,4,4],"s":[[4,4,4]]},
"s":{"0":[4,4,4],"z":[[4,4,4]],"h":[[4,4,4]],"c":{"h":[[4,4,4]]}},
"t":{
"s":{"0":[4,4,4],"z":[[4,4,4]],"c":{"h":[[4,4,4]]}},
"c":{"h":[[4,4,4]]},
"z":[[4,4,4]]
},
"h":[[3,3,3]],
"r":{"z":[[4,4,4]],"s":[[4,4,4]]}
},
"u":{
"0":[0,-1,-1],
"e":[[0,-1,-1]],
"i":[[0,1,-1]],
"j":[[0,1,-1]],
"y":[[0,1,-1]]
},
"v":[[7,7,7]],
"w":[[7,7,7]],
"x":[[5,54,54]],
"y":[[1,-1,-1]],
"z":{
"0":[4,4,4],
"d":{"0":[2,43,43],"z":{"0":[2,4,4],"h":[[2,4,4]]}},
"h":{"0":[4,4,4],"d":{"0":[2,43,43],"z":{"h":[[2,4,4]]}}},
"s":{"0":[4,4,4],"h":[[4,4,4]],"c":{"h":[[4,4,4]]}}
}
},
_map: {
а: "a", б: "b", в: "v", г: "g", д: "d", е: "e", ё: "e", ж: "zh", з: "z",
и: "i", й: "i", к: "k", л: "l", м: "m", н: "n", о: "o", п: "p", р: "r",
с: "s", т: "t", у: "u", ф: "f", х: "h", ц: "c", ч: "ch", ш: "sh", щ: "sch",
ь: "'", ы: "y", ъ: "'", э: "e", ю: "yu", я: "ya"
},
_accented: {
a: /[AaªÀ-Åà-åĀ-ąǍǎȀ-ȃȦȧᴬᵃḀḁẚẠ-ảₐ⒜ⒶⓐＡａ]/ig,
b: /[BbᴮᵇḂ-ḇℬ⒝ⒷⓑＢｂ]/ig,
c: /[CcÇçĆ-čᶜ℀ℂ℃ℭⅭⅽ⒞Ⓒⓒ㏄-㏇Ｃｃ]/ig,
d: /[DdĎďDŽ-džDZ-dzᴰᵈḊ-ḓⅅⅆⅮⅾ⒟ⒹⓓＤｄ]/ig,
e: /[EeÈ-Ëè-ëĒ-ěȄ-ȇȨȩᴱᵉḘ-ḛẸ-ẽₑℯℰⅇ⒠ⒺⓔＥｅ]/ig,
f: /[FfᶠḞḟ℉ℱ℻⒡Ⓕⓕff-fflＦｆ]/ig,
g: /[GgĜ-ģǦǧǴǵᴳᵍḠḡℊ⒢ⒼⓖＧｇ]/ig,
h: /[HhĤĥȞȟʰᴴḢ-ḫẖℋ-ℎ⒣ⒽⓗＨｈ]/ig,
i: /[IiÌ-Ïì-ïĨ-İIJijǏǐȈ-ȋᴵᵢḬḭỈ-ịⁱℐℑℹⅈ⒤ⒾⓘＩｉ]/ig,
j: /[JjIJ-ĵLJ-njǰʲᴶⅉ⒥ⒿⓙⱼＪｊ]/ig,
k: /[KkĶķǨǩᴷᵏḰ-ḵK⒦ⓀⓚＫｋ]/ig,
l: /[LlĹ-ŀLJ-ljˡᴸḶḷḺ-ḽℒℓⅬⅼ⒧ⓁⓛＬｌ]/ig,
m: /[MmᴹᵐḾ-ṃ℠™ℳⅯⅿ⒨ⓂⓜＭｍ]/ig,
n: /[NnÑñŃ-ʼnNJ-njǸǹᴺṄ-ṋⁿℕ№⒩ⓃⓝＮｎ]/ig,
o: /[OoºÒ-Öò-öŌ-őƠơǑǒǪǫȌ-ȏȮȯᴼᵒỌ-ỏₒℴ⒪ⓄⓞＯｏ]/ig,
p: /[PpᴾᵖṔ-ṗℙ⒫Ⓟⓟ㎀㎊㎩Ｐｐ]/ig,
q: /[Qqℚ⒬Ⓠⓠ㏃Ｑｑ]/ig,
r: /[RrŔ-řȐ-ȓʳᴿᵣṘ-ṛṞṟ₨ℛ-ℝ⒭ⓇⓡＲｒ]/ig,
s: /[SsŚ-šſȘșˢṠ-ṣ₨℁℠⒮ⓈⓢstＳｓ]/ig,
t: /[TtŢ-ťȚțᵀᵗṪ-ṱẗ℡™⒯Ⓣⓣ㏏ſtstＴｔ]/ig,
u: /[UuÙ-Üù-üŨ-ųƯưǓǔȔ-ȗᵁᵘᵤṲ-ṷỤ-ủ℆⒰Ⓤⓤ㍳㍺Ｕｕ]/ig,
v: /[VvᵛᵥṼ-ṿ⒱ⓋⓥⱽＶｖ]/ig,
w: /[WwŴŵʷᵂẀ-ẉẘ⒲ⓌⓦＷｗ]/ig,
x: /[XxˣẊ-ẍₓ⒳Ⓧⓧ㏓Ｘｘ]/ig,
y: /[YyÝýÿŶ-ŸȲȳʸẎẏẙỲ-ỹ⒴ⓎⓨＹｙ]/ig,
z: /[ZzŹ-žDZ-dzᶻẐ-ẕℤℨ⒵ⓏⓩＺｚ]/ig
},
_cache: {},
word(str, isCyrillic = true) {
var length = str.length,
result = "",
i = 0,
previousCode = -1,
maxLength = 6,
code;
while(i < length) {
var current = last = this._codes[str[i]];
for(var j = k = 1; k <= maxLength; k++) {
if(!str[i + k] || !current[str[i + k]]) break;
current = current[str[i + k]];
if(current[0]) {
last = current;
j = k + 1;
}
}
if(i === 0)
code = last[0][0];
else
code = (isCyrillic || "1" in last === false ? last[0] : last[1])[
str[i + j] && this._codes[str[i + j]][0][0] === 0 ? 1 : 2
];
if(code !== -1 && code !== previousCode) result += code;
previousCode = code;
i += j;
}
while(result && result.length < 3)
result += "0";
return result;
},
calculate(str) {
str = str.trim().toLowerCase();
var cyrillicMatch = str.match(/[ёа-я]/g);
if(cyrillicMatch)
str = this.transliterate(str, cyrillicMatch);
for(var letter in this._accented)
str = str.replace(this._accented[letter], letter);
str = str
.replace(/[^\sa-z]/g, "")
.replace(/\s{2,}/g, " ");
if(!str) return [];
str = str.split(" ").map(word => {
if(word in this._cache === false)
this._cache[word] = this.word(word, cyrillicMatch !== null);
return this._cache[word];
});
Object.assign(this, str);
this.length = str.length;
},
transliterate(str, matches) {
for(const match of matches)
str = str.replace(match, this._map[match]);
return str;
},
toString() {
return this.join(" ");
}
};
function Rx(template, ...substitutions) {
if(this instanceof Rx === false) return new Rx(template, ...substitutions);
this.raw = template[0] + substitutions.map((v, i) => `(${v.source})${template[i + 1]}`).join("");
this.pattern = (template.slice(1).map((part, index) => `(${substitutions[index].source}) ${Soundex(part)}`));
this.pattern.unshift(Soundex(template[0]));
this.pattern = new RegExp(this.pattern.join(" ").trim());
}
Rx.prototype = {
test(expression) {
return this.pattern.test(Soundex(expression));
},
match(expression) {
return (this.pattern.exec(Soundex(expression)) || []).slice(1);
}
};
// пример
const patterns = [
Rx`Есть ли в наличии ${/[\s\S]+/}?`,
Rx`Есть ли ${/[\s\S]+/} в наличии?`,
];
inputField.addEventListener("input", () => {
patternsField.innerHTML = patterns.map(pattern => {
const ok = pattern.test(inputField.value);
return `<div class="${ok ? "matches" : ""}">${pattern.raw}</div>`;
}).join("");
});
inputField.dispatchEvent(new Event("input"));
</script>
</body>
</html>
[1]: Paramonov V., Shigarov A., Ruzhnikov G., Belykh P. Polyphon: An Algorithm for Phonetic String Matching in Russian Language // Communications in Computer and Information Science. Springer. 2016. Vol. 639, pp. 568-579. |
давно такого дерьма не смотрел, как уснуть то теперь
|
Malleys, Это гениально.
Большое спасибо за столь развернутый ответ, отдельное спасибо за пример. К сожалению из-за ограничений сайта не могу вам карму увеличить. |
| Часовой пояс GMT +3, время: 03:43. |