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

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

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

本例对最长公共子字符串进行两次迭代并输出结果:

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