java - 如何从文件名集合中推断出模式？

Question

我想知道是否有一种众所周知的算法可以在给定示例文件名集合作为输入的情况下推断文件名模式。采用以下示例文件名:

  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 库都是理想的解决方案。否则，如果这个问题有一个众所周知的算法，那么我可以自己实现。

Answer 1

假设您只想基于常见子字符串建议通配符模式，则可以使用 longest common substring algorithm计算所有公共(public)子串，然后根据其长度和出现次数选择一些。这可以递归地完成，以找到更常见的子字符串。

此示例对 longest common substring 进行 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