10

* ワイルドカードを含む 2 つの文字列が与えられた場合、両方に一致する文字列を作成できるかどうかを知りたいです。

たとえば、次の 2 つは重複の単純なケースです。

  1. こんにちは世界
  2. ヘル*

しかし、これらすべても同様です。

  1. *.csv
  2. レポート*.csv
  3. レポートダンプ.csv

これを行うために公開されているアルゴリズムはありますか? それとも、Windows のユーティリティ関数や、呼び出しまたはコピーできるライブラリでしょうか?

4

5 に答える 5

8

すべてのグロブは正規表現として記述でき、2 つの正規表現の交点を見つけることができるため (実際には規則的でない場合を除きますが、この場合はそうなります)、2 つのグロブを次のように変換して交点を見つけることができます。正規表現を作成し、それらの交点を見つけます。したがって、正規表現の交点を見つけて、それが空かどうかをチェックすることで、2 つのグロブが交差しているかどうかを調べることができます。

ただし、グロブは正規表現よりも制限があるため、はるかに簡単な方法があります。

2 つのグロブを g1 と g2 と呼びましょう。それらは交差します

  1. g1 と g2 の両方が空であるか、ワイルドカードのみが含まれています。
  2. g1 も g2 も空ではなく、次の条件のいずれかが真です (c1 を g1 の最初の文字とし、t1 を残りの文字を含む文字列とします。g2 と c2 および t2 も同じです)。
    1. c1 と c2 が等しく、t1 と t2 が交差する
    2. c1 および/または c2 がワイルドカードであり、t1 が g2 と交差する
    3. c1 および/または c2 はワイルドカードであり、g1 は t2 と交差します

haskell での実装例:

intersect g1          []          = all (== '*') g1
intersect []          g2          = all (== '*') g2
intersect g1@('*':t1) g2@(c2:t2)  = intersect g1 t2 || intersect t1 g2
intersect g1@(c1:t1)  g2@('*':t2) = intersect t1 g2 || intersect g1 t2
intersect    (c1:t1)     (c2:t2)  = c1 == c2        && intersect t1 t2

グロブに多くのワイルドカードが含まれている場合、このアルゴリズムは特に効率的ではありませんが、実装は非常に簡単です。おそらくファイル名でこれを使用する予定であるため、グロブが 1000 文字を超えることはないと思います。

于 2010-07-09T13:59:28.583 に答える
1

価値があるのは、C＃でのsepp2kの回答からのアルゴリズムの1つの実装です（アルゴリズムの読みやすさのために、コメントとともに明示的な呼び出しを使用しました）return true;：return false;

public static bool WildcardIntersect(string w1, string w2)
{
    // if both are empty or contain wildcards
    if ((string.IsNullOrEmpty(w1) || w1 == "*")
        && (string.IsNullOrEmpty(w2) || w2 == "*"))
        return true;

    // if either string is empty, return false
    // we can do this because we know the other string MUST be non-empty and non-wildcard
    if (string.IsNullOrEmpty(w1) || string.IsNullOrEmpty(w2))
        return false;

    char c1 = w1[0], // first character of wildcard string 1
         c2 = w2[0]; // first character of wildcard string 2
    string remain1 = w1.Substring(1), // remaining of wildcard string 1
           remain2 = w2.Substring(1); // remaining of wildcard string 2

    // if first letters match and remaining intersect
    if ((c1 == c2 && WildcardIntersect(remain1, remain2))
        // if either is a wildcard and either remaining intersects with the other whole
        || ((c1 == '*' || c2 == '*') && (WildcardIntersect(w1, remain2) || WildcardIntersect(remain1, w2))))
        return true;

    // else, no match, return false
    return false;
}
于 2011-05-19T14:47:04.467 に答える
0

私が理解しているように、正規表現が別の正規表現と直交しているかどうかを判断しようとしていますか? もしそうなら、これは些細な問題ではありません。

理論についてはこちら。

これが解決策です：Javaライブラリ。

使用法：

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}
于 2013-07-30T20:58:47.113 に答える