🤙🏽 🍧 👬 プレフィックスJava正規表現の最適化 👩‍👩‍👦 👨🏾‍🔧 😅

正規表現、または辞書を最適化する簡単な方法についてお話したいと思います。有限状態マシン、テキスト内の辞書のクイックマークアップを実行するパッケージを最適化するプロジェクトを見ましたが、辞書を取得して、正規表現エンジンに渡すことができる正規表現をまとめるだけです。まだ見ていません。

問題は、都市の巨大な辞書があり、テキスト内のこれらすべてのフレーズを見つける必要があるということです。素朴なアプローチは、orでこれらの単語を結合することであるため、この表現が得られます（city1 | city2 | city3 | ... cityN）。そのような表現を処理するとき、通常のNDAエンジン（JDKを含む多数派）は、最悪の場合（現在の単語が辞書のすべての単語と辞書の最後の単語と異なる場合）、テキストの各文字に対して少なくともNチェックを行いますチェックは辞書の文字数に等しくなります。

これは悪いですが、もっとうまくやることができます。

言語の典型的な特性は冗長性です。この場合、文字列の繰り返し性です。ここでは、最も簡単な最適化方法であるプレフィックス最適化について説明します。

単語が同じプレフィックスで始まる場合、計算はプレフィックスに対して1回実行されます。したがって、辞書に従ってTrieを構築し、それを正規表現文字列に変換します。

ツリークラス

class Node { char ch = START; List<Node> nodes = Lists.newArrayList(); void add(String str) { if (str.length() == 0) return; char chNew = str.charAt(0); for (Node n : nodes) { if (n.ch == chNew) { n.add(str.substring(1)); return; } } Node newNode = new Node(); newNode.ch = chNew; newNode.add(str.substring(1)); nodes.add(newNode); } String toRegexp() {...} }

メインのaddメソッドは、子の中に最初の文字があるかどうかを確認します。ない場合は、この文字で始まるサブツリーを作成して提供します。

したがって、この構造では、プレフィックスは1回（ツリーを通るパス）だけ保存され、行で発生したときに再利用されます。

2番目の方法は、ツリーを正規表現に変換します。

  String toRegexp() { StringBuilder str = new StringBuilder(); if (ch == START) { } else if (ch == END) { } else { //convert special characters like {}[]. String newStr = escapeRegexp(String.valueOf(ch)); str.append(newStr); } if (nodes.size() > 1) { str.append("(?:"); for (Node n : nodes) { str.append(""); str.append(n.toRegexp()); str.append("|"); } str.setLength(str.length() - 1); str.append(')'); } else if (nodes.size() == 1) { str.append(nodes.get(0).toRegexp()); } return str.toString(); } }

ここに作業コードがあります

 public static String convertListToRegexp(final boolean useNonCapturingGroups, String... strs) { Arrays.sort(strs, new Comparator<String>() { public int compare(String o1, String o2) { int res = o2.length() - o1.length(); if (res != 0) { return res; } return o1.compareTo(o2); } }); Node root = new Node(); for (String str : strs) { root.add(str + "$"); } return root.toRegexp(); }

そして例

 //create array of your entries String[] examples = new String[]{"javvva", "javggaaa", "javajava", "adsasd", "adasddsa"}; //convert them to optimal regexp String optimizedRegexp = RegExpUtils.convertListToRegexp(true, examples); Assert.assertEquals("(?:ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva))", optimizedRegexp); //check that it is works for(String s : examples) Assert.assertTrue(s.matches(optimizedRegexp));

プレフィックスJava正規表現の最適化

More articles: