java - 正規表現辞書検索使い捨て文字

Question

私は、特定の文字セットで構成される単語を辞書で検索するJavaプログラムに取り組んでいます。文字列に表示される回数だけ文字を使用できる正規表現を設定できるかどうか疑問に思っています。たとえば、SHAREという文字を使用します。聞く、うさぎ、海などが有効です。ただし、eまたはsarahは、それぞれ1つまたは1つしかないため、有効ではありません。

Answer 1

正規表現はパターン マッチングに関するものです。単純なパターンを見つけることはおそらく不可能でしょう。

本当に本当に正規表現が必要な場合は、これらの関数が生成します。

public  static String permutation(String str) {
    return "^" + permutation("",str).replaceFirst("\\|", "(") + ")$";
 }

 private static String permutation(String prefix, String str) {
    String s = "";
    int n = str.length();
    if (n == 0) return "|"+prefix;
    else {
        for (int i = 0; i < n; i++)
           s += permutation(prefix + str.charAt(i)+"?",
                            str.substring(0, i) + str.substring(i+1, n));
    }
    return s;
}

「共有」の場合、次が返されます。

^(s?h?a?r?e?|s?h?a?e?r?|s?h?r?a?e?|s?h?r?e?a?|s?h?e?a?r?|s?h?e?r?a?|s?a?h?r?e?|s?a?h?e?r?|s?a?r?h?e?|s?a?r?e?h?|s?a?e?h?r?|s?a?e?r?h?|s?r?h?a?e?|s?r?h?e?a?|s?r?a?h?e?|s?r?a?e?h?|s?r?e?h?a?|s?r?e?a?h?|s?e?h?a?r?|s?e?h?r?a?|s?e?a?h?r?|s?e?a?r?h?|s?e?r?h?a?|s?e?r?a?h?|h?s?a?r?e?|h?s?a?e?r?|h?s?r?a?e?|h?s?r?e?a?|h?s?e?a?r?|h?s?e?r?a?|h?a?s?r?e?|h?a?s?e?r?|h?a?r?s?e?|h?a?r?e?s?|h?a?e?s?r?|h?a?e?r?s?|h?r?s?a?e?|h?r?s?e?a?|h?r?a?s?e?|h?r?a?e?s?|h?r?e?s?a?|h?r?e?a?s?|h?e?s?a?r?|h?e?s?r?a?|h?e?a?s?r?|h?e?a?r?s?|h?e?r?s?a?|h?e?r?a?s?|a?s?h?r?e?|a?s?h?e?r?|a?s?r?h?e?|a?s?r?e?h?|a?s?e?h?r?|a?s?e?r?h?|a?h?s?r?e?|a?h?s?e?r?|a?h?r?s?e?|a?h?r?e?s?|a?h?e?s?r?|a?h?e?r?s?|a?r?s?h?e?|a?r?s?e?h?|a?r?h?s?e?|a?r?h?e?s?|a?r?e?s?h?|a?r?e?h?s?|a?e?s?h?r?|a?e?s?r?h?|a?e?h?s?r?|a?e?h?r?s?|a?e?r?s?h?|a?e?r?h?s?|r?s?h?a?e?|r?s?h?e?a?|r?s?a?h?e?|r?s?a?e?h?|r?s?e?h?a?|r?s?e?a?h?|r?h?s?a?e?|r?h?s?e?a?|r?h?a?s?e?|r?h?a?e?s?|r?h?e?s?a?|r?h?e?a?s?|r?a?s?h?e?|r?a?s?e?h?|r?a?h?s?e?|r?a?h?e?s?|r?a?e?s?h?|r?a?e?h?s?|r?e?s?h?a?|r?e?s?a?h?|r?e?h?s?a?|r?e?h?a?s?|r?e?a?s?h?|r?e?a?h?s?|e?s?h?a?r?|e?s?h?r?a?|e?s?a?h?r?|e?s?a?r?h?|e?s?r?h?a?|e?s?r?a?h?|e?h?s?a?r?|e?h?s?r?a?|e?h?a?s?r?|e?h?a?r?s?|e?h?r?s?a?|e?h?r?a?s?|e?a?s?h?r?|e?a?s?r?h?|e?a?h?s?r?|e?a?h?r?s?|e?a?r?s?h?|e?a?r?h?s?|e?r?s?h?a?|e?r?s?a?h?|e?r?h?s?a?|e?r?h?a?s?|e?r?a?s?h?|e?r?a?h?s?)$

明らかに、これはかなり単純化して最適化することができますが、それでも良いアイデアではありません。

EDIT：短い出力のための機能：

public  static String permutation(String str) {
    return "^(" + permutation("",str) + ")$";
 }

 private static String permutation(String prefix, String str) {
   String s = "";
   int n = str.length();
   if (n == 0) return prefix;
   else {
     for (int i = 0; i < n; i++)
       if (i != n-1)
         s += prefix + str.charAt(i) + "?(" +
            permutation("", str.substring(0, i) + str.substring(i+1, n))+")|";
       else
         s += prefix + str.charAt(i) + "?" +
            permutation("", str.substring(0, i) + str.substring(i+1, n));
   }
   return s;
}

版画:

^(s?(h?(a?(r?(e?)|e?r?)|r?(a?(e?)|e?a?)|e?a?(r?)|r?a?)|a?(h?(r?(e?)|e?r?)|r?(h?(e?)|e?h?)|e?h?(r?)|r?h?)|r?(h?(a?(e?)|e?a?)|a?(h?(e?)|e?h?)|e?h?(a?)|a?h?)|e?h?(a?(r?)|r?a?)|a?(h?(r?)|r?h?)|r?h?(a?)|a?h?)|h?(s?(a?(r?(e?)|e?r?)|r?(a?(e?)|e?a?)|e?a?(r?)|r?a?)|a?(s?(r?(e?)|e?r?)|r?(s?(e?)|e?s?)|e?s?(r?)|r?s?)|r?(s?(a?(e?)|e?a?)|a?(s?(e?)|e?s?)|e?s?(a?)|a?s?)|e?s?(a?(r?)|r?a?)|a?(s?(r?)|r?s?)|r?s?(a?)|a?s?)|a?(s?(h?(r?(e?)|e?r?)|r?(h?(e?)|e?h?)|e?h?(r?)|r?h?)|h?(s?(r?(e?)|e?r?)|r?(s?(e?)|e?s?)|e?s?(r?)|r?s?)|r?(s?(h?(e?)|e?h?)|h?(s?(e?)|e?s?)|e?s?(h?)|h?s?)|e?s?(h?(r?)|r?h?)|h?(s?(r?)|r?s?)|r?s?(h?)|h?s?)|r?(s?(h?(a?(e?)|e?a?)|a?(h?(e?)|e?h?)|e?h?(a?)|a?h?)|h?(s?(a?(e?)|e?a?)|a?(s?(e?)|e?s?)|e?s?(a?)|a?s?)|a?(s?(h?(e?)|e?h?)|h?(s?(e?)|e?s?)|e?s?(h?)|h?s?)|e?s?(h?(a?)|a?h?)|h?(s?(a?)|a?s?)|a?s?(h?)|h?s?)|e?s?(h?(a?(r?)|r?a?)|a?(h?(r?)|r?h?)|r?h?(a?)|a?h?)|h?(s?(a?(r?)|r?a?)|a?(s?(r?)|r?s?)|r?s?(a?)|a?s?)|a?(s?(h?(r?)|r?h?)|h?(s?(r?)|r?s?)|r?s?(h?)|h?s?)|r?s?(h?(a?)|a?h?)|h?(s?(a?)|a?s?)|a?s?(h?)|h?s?)$

Answer 2

パターン マッチングを使用しないが、問題の根本に到達するアプローチは、ターゲット ワードの各文字数を含む配列を作成することです。「deaf」は配列 (1,0,0,1 ,1,1,0,0,...)。

次に、辞書をループするときに、単語ごとに同じ配列を準備し、それをターゲット単語の配列から減算します。違いの配列に負の値がある場合、その単語はその文字から構成できません。対象ワード。

Answer 3

これを行う方法の例を次に示します。ただし、壊滅的なバック トラッキングに関する次の記事を読む必要があります。

ランナウェイ正規表現: 壊滅的なバックトラッキング

正規表現のパフォーマンス

^(?!.*s.*s)(?!.*h.*h)(?!.*a.*a)(?!.*r.*r)(?!.*e.*e)(?![^share]).*$

共有のような 2 文字の「s」を許可して、sashes という単語を許可したい場合は、次のようにすることができます。

^(?!.*s.*s.*s)(?!.*h.*h)(?!.*a.*a)(?!.*r.*r)(?!.*e.*e)(?![^share]).*$

単語の「s」が 3 つ未満のアイデアは問題ありません...

Answer 4

ここに1つのアプローチがあります：

1. 文字列配列を繰り返し処理してMultiMap<String, String>(Guava ライブラリを使用しているHashMap<String, List<String>>場合、または java.util を使用している場合) を作成します。ここで、キーは並べ替えられた単語であり、値はその並べ替えられた文字列の有効な単語です。これは前処理ステップになるため、これを行う必要があるのは 1 回だけです。ハッシュマップが既に存在するため、後続の検索は比較的高速になります (ハッシュマップを使用するよりもはるかに遅くなる正規表現と一致するたびに辞書をループすることに比べて)。
2. 検索文字列を並べ替え、その並べ替えられた文字列のすべての部分文字列を見つけます。
3. 並べ替えられたサブセットを反復処理し、HashMap または MultiMap を検索して、その並べ替えられたサブセット文字列の値を取得します。すべての値を追跡すると、答えが得られます。

ここでの問題は、検索ごとに辞書全体をループする必要があるため（配列として保存した）、正規表現が説明に適していないことだと思います。一方、ハッシュマップを作成する場合 (このステップは比較的高価です)、ソートされたサブセット リストをループするだけです (これは安価です)。

Answer 5

にはないため、単語に2回現れる文字がない場合はshare、次を使用できます

^(?!([share]).*\\1)[share]+$

これは、 の一部またはすべての文字で構成される任意の単語に一致しshareます。

(?!)括弧内で一致したものへの後方参照を含む否定先読み\\1は、文字が複数回出現する場合に一致を防ぎます。

この原則を拡張して、文字が複数回出現する単語を処理できます。