1

何千ものファイルが次のように整理されているとします。最初にファイル名で並べ替え (大文字と小文字が区別されるため、大文字のファイルが小文字のファイルよりも前になります)、次にファイルを最初のファイルの名前と最初のファイルの名前を含むフォルダーにグループ化します。そのフォルダの最後のファイル。たとえば、フォルダは次のようになります。

Abel -> Cain
Camel -> Sloth
Stork -> basket
basking -> sleuth
tiger -> zebra

次に、大文字と小文字を区別しない検索文字列を指定sして、一致するファイルを格納できるフォルダーを決定しますs。フォルダの中を見ることはできませんし、見る必要もありません。ファイルが実際に存在する必要はありません。

いくつかの例：

("Abel", "Cain")    matches s = "blue",   since it contains "Blue"
("Stork", "basket") matches s = "arctic", since it contains "arctic"
("FA", "Fb")        matches s = "foo",    since it contains "FOo"
("Fa", "Fb") does NOT match s = "foo"

正式には: 閉じた範囲[a,b]と小文字の stringが与えられた場合、その中に文字列がsあるかどうかを判断します。c[a,b]lower(c) = s

私の最初の直感は、範囲の境界に対して大文字と小文字を区別しない検索を行うことでした。しかし、これが正しくないことは、最後の例から簡単にわかります。

強引な解決策は、すべての潜在的なファイル名を生成することです。たとえば、入力文字列"abc"は候補を生成し"ABC", "ABc", "AbC", "Abc", "aBC", "aBc", "abC", "abc"ます。次に、境界に対してそれぞれをテストします。このブルート フォース ソリューションの例を以下に示します。これはO(2^n)だけど。

私の質問は、高速で正しいアルゴリズムがあるかどうかです。

Clojure でのブルート フォース ソリューション:

(defn range-contains 
  [first last string]
  (and (<= (compare first string) 0)
       (>= (compare last string) 0)))

(defn generate-cases
  "Generates all lowercase/uppercase combinations of a word"
  [string]
  (if (empty? string)
    [nil]
    (for [head [(java.lang.Character/toUpperCase (first string))
                (java.lang.Character/toLowerCase (first string))]
          tail (generate-cases (rest string))]
      (cons head tail))))

(defn range-contains-insensitive 
  [first last string]
  (let [f (fn [acc candidate] (or acc (range-contains first last (apply str candidate))))]
    (reduce f false (generate-cases string))))

(fact "Range overlapping case insensitive"
  (range-contains-insensitive "A" "Z" "g") => true
  (range-contains-insensitive "FA" "Fa" "foo") => true
  (range-contains-insensitive "b" "z" "a") => false
  (range-contains-insensitive "B" "z" "a") => true)
4

2 に答える 2

1

大文字と小文字の組み合わせをすべて作成するのではなく、文字ごとに個別に大文字、次に小文字をチェックし、2^N を 2N に変更することで解決できると思います。

アイデアは次のとおりです。

  • "lowdone" フラグと "highdone" フラグを保持します。これは、s が確実に下限を超えても、上限を超える可能性があるかどうか、およびその逆も可能かどうかを示します。
  • 文字列を 1 文字ずつ移動する
  • 現在の文字の大文字バージョンが、対応する下限文字の後に来ると同時に上限文字の前に来ることができるかどうかを確認し、小文字バージョンの文字についても同じことを確認します。どちらの文字も両方の条件を満たさない場合は、false を返します。 (「lowdone」が true の場合は下限をチェックしない、「highdone」が true の場合は上限をチェックしない - ABC と ACA を比較する場合、2 番目の文字を過ぎたら、3 番目の文字は気にしません。 )
  • ケースが両方の条件を満たす場合は、下限文字の後に厳密に来るか、または下限が短すぎて対応する文字がないかを確認します。そうであれば、lowdone = true
  • highdone = true に類似

これはいい音ですか？C# のコード (おそらくもっと簡潔に記述できます):

        public Bracket(string l, string u)
        {
            Low = l;
            High = u;
        }

        public bool IsMatch(string s)
        {
            string su = s.ToUpper();
            string sl = s.ToLower();

            bool lowdone = false;
            bool highdone = false;
            for (int i = 0; i < s.Length; i++)
            {
                char[] c = new char[]{su[i], sl[i]};

                bool possible = false;
                bool ld = lowdone;
                bool hd = highdone;
                for (int j = 0; j < 2; j++)
                {
                    if ((lowdone || i >= Low.Length || c[j] >= Low[i]) && (highdone || i >= High.Length || c[j] <= High[i]))
                    {
                        if (i >= Low.Length || c[j] > Low[i])
                            ld = true;

                        if (i >= High.Length || c[j] < High[i])
                            hd = true;

                        possible = true;
                    }
                }
                lowdone = ld;
                highdone = hd;

                if (!possible)
                    return false;
            }

            if (!lowdone && Low.Length > s.Length)
                return false;

            return true;
        }
    }
于 2013-07-02T07:59:02.827 に答える
0

完全な開示の精神で、思いついたアルゴリズムも追加する必要があると思います（Java、Guavaを使用）：

public static boolean inRange(String search, String first, String last) {
    int len = search.length();
    if (len == 0) {
        return true;
    }

    char low = Strings.padEnd(first, len, (char) 0).charAt(0);
    char high = Strings.padEnd(last, len, (char) 0).charAt(0);

    char capital = Character.toLowerCase(search.charAt(0));
    char small = Character.toUpperCase(search.charAt(0));

    if (low == high) {
        if (capital == low || small == low) {
            // All letters equal - remove first letter and restart
            return inRange(search.substring(1), first.substring(1), last.substring(1));
        }
        return false;
    }

    if (containsAny(Ranges.open(low, high), capital, small)) {
        return true; // Definitely inside
    }

    if (!containsAny(Ranges.closed(low, high), capital, small)) {
        return false; // Definitely outside
    }

    // Edge case - we are on a bound and the bounds are different
    if (capital == low || small == low) {
        return Ranges.atLeast(first.substring(1)).contains(search.substring(1).toLowerCase());
    }
    else {
        return Ranges.lessThan(last.substring(1)).contains(search.substring(1).toUpperCase());
    }
}

private static <T extends Comparable<T>> boolean containsAny(Range<T> range, T value1, T value2) {
    return range.contains(value1) || range.contains(value2);
}
于 2013-07-02T09:04:48.970 に答える