1

入力としてサンプル ファイル名のコレクションが与えられた場合に、ファイル名パターンを外挿するためのよく知られたアルゴリズムがあるかどうかを知りたいです。次のファイル名の例を見てください。

  ABC_348093423.csv
i.ABC_348097340.csv
  ABC_348099322.csv
i.GHI_348099324.csv
p.ABC_348101632.csv
  DEF_348101736.csv
p.ABC_348101633.csv
  ABC_348102548.csv

理想的には、結果セットで最終的に得たいパターンは次のようになります。

*.ABC_*.csv
*.DEF_*.csv
*.GHI_*.csv

次のような結果値であっても、出発点としては適切です。

i.ABC_348*.csv
p.ABC_348*.csv
...

なぜこれが必要なのですか？

ユーザーが「ファイルマスク」を入力して、受信入力ファイルをグループ化するためのバケットを定義できる既存のアプリケーションがあります。着信ファイルは各ファイル マスクに対して (順番に) 評価され、ファイルがマスクと一致する場合、ファイルはそのファイル マスクのバケットに入れられます... 最後です。

私が実装したいのは、処理された最後の X ファイル名を考慮して、ユーザーに新しいファイル マスクの提案を提示することです。完璧である必要はありません。これは単なるユーザーアシスト機能です。

使用している言語は何ですか?

私のアプリケーションは Java で書かれているので、この種の機能を実行できるサードパーティの Java ライブラリは理想的なソリューションです。そうでなければ、この問題に対するよく知られたアルゴリズムがあれば、それを自分で実装できます。

4

1 に答える 1

0

共通部分文字列に基づいてワイルドカード パターンを提案したいだけだと仮定すると、最長共通部分文字列アルゴリズムを使用してすべての共通部分文字列を計算し、その長さと出現回数に基づいていくつかを選択できます。これを再帰的に実行して、より一般的な部分文字列を見つけることができます。

この例では、最長の共通部分文字列を2 回反復し、結果を出力します。

import java.util.*;

public class Main {

    private static String longestCommonSubstring(String S1, String S2)
    {
        int Start = 0;
        int Max = 0;
        for (int i = 0; i < S1.length(); i++)
        {
            for (int j = 0; j < S2.length(); j++)
            {
                int x = 0;
                while (S1.charAt(i + x) == S2.charAt(j + x))
                {
                    x++;
                    if (((i + x) >= S1.length()) || ((j + x) >= S2.length())) break;
                }
                if (x > Max)
                {
                    Max = x;
                    Start = i;
                }
            }
        }
        return S1.substring(Start, (Start + Max));
    }



    public static SortedMap<String,Integer> commonSubstrings(List<String> strings) {
        SortedMap<String,Integer> subs = new TreeMap<>();
        for (String str1: strings) {
            for (String str2: strings) {
                if (str1 != str2) {
                    String sub = longestCommonSubstring(str1,str2);
                    if (subs.containsKey(sub))
                        subs.put(sub,subs.get(sub)+1);
                    else
                        subs.put(sub,1);
                }
            }
        }

        return subs;
    }


    public static void main(String[] args) {
        List<String> filenames = Arrays.asList(
                "ABC_348093423.csv",
                "i.ABC_348097340.csv",
                "ABC_348099322.csv",
                "i.GHI_348099324.csv",
                "p.ABC_348101632.csv",
                "DEF_348101736.csv",
                "p.ABC_348101633.csv",
                "ABC_348102548.csv");

        Map<String,Integer> substrings = commonSubstrings(filenames);

        Map<String,Integer> subsubstrings = commonSubstrings(new ArrayList<>(substrings.keySet()));

        List<Map.Entry<String,Integer>> results = new ArrayList<>(subsubstrings.entrySet());
        Collections.sort(results, (a,b) -> a.getValue().compareTo(b.getValue()));

        for ( Map.Entry<String,Integer> s: results ) {
            System.out.println(s.getKey() + "\t" + s.getValue());
        }
    }
}

もちろん、これは次のようなすべてのファイル名に共通する短い部分文字列を見逃しています.csv

于 2014-07-28T19:05:39.910 に答える