Skip to content

Instantly share code, notes, and snippets.

@DenVdmj
Created Jun 13, 2018
Embed
What would you like to do?
RegExp Optimization (es6)
<html>
<head>
<title>RegExp optimization</title>
<meta charset="utf-8" />
</head>
<body>
<h1>RegExp Optimization</h1>
<button create-regexp>Create RegExp from words list</button>
<textarea input>
a, abbr, acronym, address, applet, area,
b, base, basefont, bdo, big, blockquote, body, br, button,
caption, center, cite, code, col, colgroup,
dd, del, dfn, dir, div, dl, dt, em,
fieldset, font, form, frame, frameset,
h1, h2, h3, h4, h5, h6, head, hr, html,
i, iframe, img, input, ins, isindex, kbd,
label, legend, li, link, map, menu, meta, nobr, noframes, noscript,
object, ol, optgroup, option, p, param, pre, q,
s, samp, script, select, small, span, strike, strong, style, sub, sup,
table, tbody, td, textarea, tfoot, th, thead, title, tr, tt, u, ul, var
</textarea>
<textarea output></textarea>
<output></output>
<h2>Оптимизация регулярных выражений</h2>
<p>Портировано на javascript c java-кода опубликованного в статье <a href="http://habrahabr.ru/post/117177/">http://habrahabr.ru/post/117177/</a></p>
<p>В коде оставлены оригинальные комментарии <a href="https://habrahabr.ru/users/yuk/">автора</a></p>
<p>ES5 версия: <a href="https://codepen.io/DenVdmj/pen/MGNejb">https://codepen.io/DenVdmj/pen/MGNejb</a></p>
</body>
</html>
//
// Оптимизация регулярных выражений.
// Портировано на javascript c java-кода опубликованного
// в статье http://habrahabr.ru/post/117177/
// В коде оставлены оригинальные комментарии автора.
// https://habrahabr.ru/users/yuk/
// ES5 версия: https://codepen.io/DenVdmj/pen/MGNejb
//
(() => {
class RENode {
constructor () {
this.ch = '';
this.nodes = [];
}
add (str) {
if (str.length === 0) return;
const chNew = str.charAt(0);
const node = this.nodes.find(n => n.ch === chNew);
if (node) {
node.add(str.substring(1));
return;
}
const newNode = new RENode();
newNode.ch = chNew;
newNode.add(str.substring(1));
this.nodes.push(newNode);
}
// Как мы видим его основной метод add проверяет есть ли первый символ среди его детей,
// если нет, то создает и отдает тому поддереву, которое начинается с этого символа.
// Таким образом в данной структуре любой префикс хранится только один раз (путь по дереву)
// и переиспользуется когда встречается в наших строках.
// Второй метод конвертирует дерево в регулярное выражение.
toRegExp () {
const union = this.nodes.map(n => n.toRegExp()).join('|');
return escapeRegexp(this.ch) + (this.nodes.length > 1 ? `(?:${union})` : union);
}
}
const escapeRegexp = re => re.replace(/[\*\!\?\:\[\]\(\)\{\}\.\|]/g, '\\$&');
// Вот рабочий код
RegExp.newFromList = strings => {
strings.sort((a, b) => a != b ? a > b ? 1 : -1 : 0);
const root = new RENode();
for (let str of strings) {
root.add(str + '$');
}
return root.toRegExp();
};
})();
document.querySelector('button[create-regexp]').onclick = () => {
document.querySelector('textarea[output]').value = (
RegExp.newFromList(
document.querySelector('textarea[input]').value.trim().split(/\s*,\s*/)
) + ''
)
}
body {
background: #E0E0E0;
color: #000;
text-shadow: 0 0 4px #fff;
font: 17px/1.36 Roboto, Roboto Condensed, sans-serif;
font-stretch: ultra-condensed;
margin: 2rem;
}
textarea {
width: calc(100%-4rem);
max-width: 50rem;
height: 14rem;
margin: .5rem 0;
display: block;
padding: .5em 0 0 1em;
color: #444;
resize: vertical;
&:focus {
color: #000;
outline: 2px solid #92AFED;
}
}
output {
clear: both;
}
button {
display: inline-block;
border: 1px solid #B5B5B5;
background: #fff;
padding: .6em 2em .6em 2em;
margin: .1em;
text-align: center;
text-decoration: none;
border-radius: .1em;
box-shadow: 2px 2px 0 0 rgba(0,0,0,.1), inset 0 0 0 0 transparent;
transition: all .1s ease-out;
cursor: default;
outline: none;
position: relative;
user-select: none;
}
button:hover {
color: #333;
text-shadow: 0 0 0 #000;
text-shadow: #fff 0 0 2px;
box-shadow: 2px 2px 10px 0 rgba(0,0,0,.3), inset 0 0 0 0 transparent;
}
button:active {
color: #444;
background: #f8f8f8;
box-shadow: 0 0 0 0 transparent, inset 0px 18px 0 0 rgba(0,0,0,.09);
left: 1px;
top: 1px;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment