algorithm - 基于输入文本格式的分类器

Question

我正在寻找一种可以衡量两个输入文本之间格式相似性的算法(基于其构建分类器)。广义地说，格式上的 Levenshtein 距离。

例如，考虑让一个应用程序从不同来源收集日志数据，并按格式标记它们。

另一个例子是考虑一个应用程序，它接收来自不同编程语言的输入作为源代码(假设它们不相似，所以 C 和 Haskell)并且能够按它们的格式对它们进行分类。

编辑:附加示例

考虑 df -h 运行的输出

Filesystem               Size  Used Avail Use% Mounted on
/dev/mapper/fedora-root   50G   12G   35G  26% /
devtmpfs                 3.9G     0  3.9G   0% /dev
tmpfs                    3.9G  596K  3.9G   1% /dev/shm
tmpfs                    3.9G  9.1M  3.9G   1% /run
tmpfs                    3.9G     0  3.9G   0% /sys/fs/cgroup
tmpfs                    3.9G  580K  3.9G   1% /tmp
/dev/mapper/fedora-home  178G   82G   87G  49% /home
/dev/sda1                477M  147M  301M  33% /boot

这将与 ls -l

进行比较

total 68
drwxrwxr-x.  2 mhitza mhitza 4096 May 31 22:17 bin
drwxr-xr-x.  2 mhitza mhitza 4096 Jun  1 23:00 Desktop
drwxr-xr-x.  5 mhitza mhitza 4096 May 16 15:43 Documents
drwxr-xr-x. 12 mhitza mhitza 4096 Jun  4 19:08 Downloads
drwx------. 12 mhitza mhitza 4096 Mar 18 23:48 Dropbox
drwxrwxr-x. 12 mhitza mhitza 4096 Apr 30 02:08 Local

该算法应该能够推断这两个是不同类型的文本“结构”，并且能够为这些组对其他类型的传入文本进行分类。

问题是这对于一组固定的格式很容易做到，但我想对任何类型的输入都做到这一点。

Answer 1

根据我对问题的理解，您正在寻找一种表示任意文本的方法，以便可以根据数据的格式/结构而不是数据所含的值对其进行分类或聚类。

天真的方法是只为已知文档类型收集一组解析器并按顺序应用它们，但是(除了笨拙之外)我想你不想这样做，因为你希望该方法适用到任意结构(即:新​​的和/或不支持的格式)。

我的第一个想法是，当您尝试根据结构而不是内容进行分类时，应该尝试将您的文档简化为符号表示。

例如 df -h 输出:

Filesystem               Size  Used Avail Use% Mounted on
/dev/mapper/fedora-root   50G   12G   35G  26% /
...

会变成:

STRING, SEP, STRING, SEP, STRING, SEP, STRING, SEP, STRING, SEP, STRING
FILEPATH, SEP, MEMSIZE, SEP, MEMSIZE, SEP, MEMSIZE, SEP, PERCENTAGE, SEP, FILEPATH
...

例如，这可以通过应用一组不同的预定义正则表达式(不要忘记“我不知道”正则表达式)来实现。

只需执行这一步，就可以很容易地识别出 df -h 输出，因为它会有一个标题行和一堆表格行，尽管它们具有不同的值，但都具有相同的符号表示。

要将它变成有用的东西，你可以抛出 bag of words model在它上面，并将每个符号行作为一个“单词”。

按照这种方法，您可以找到一组有区别的常用“词”(也称为符号行)，您可以使用它们来创建每个文档的数字表示。这可以使用类似 term frequency–inverse document frequency 的东西来完成，但可能会受益于使用监督学习方法(可能类似于递归特征消除)。从那里开始，将它放入您最喜欢的分类或聚类算法中是一个相当简单的案例。

仅根据问题中给出的示例，它可能看起来像这样:

ls -l 输出:

total 68
drwxrwxr-x.  2 mhitza mhitza 4096 May 31 22:17 bin
...

将成为 ls -l 符号:

STRING, SEP, NUMBERS
STRING, SEP, NUMBER, SEP, STRING, SEP, STRING, SEP, NUMBERS, SEP, STRING, SEP, NUMBER, SEP, TIME, SEP, FILEPATH
...

为简洁起见，我们将这些符号行称为L1 和L2，df -h 符号行也类似D1 和 D2。这意味着我们可以如下表示两个示例文档:

ls -l: D1:0, D2:0, L1:1, L2:6
df -h: D1:1, D2:8, L1:0, L2:0