2010-04-03 39 views
1

好吧,伙计们,我真的伤害了我的大脑,而我很好奇,如果你们能给我任何指向我应该采取的正确方向。基于未知模式匹配无与伦比的字符串

的情况是这样的:

比方说,我有一个字符串(让它很清楚,这个字符串的模式是未知的一个事实,我可以说,该字符串只包含从招牌的集合。 ASCII表,因此,我不必担心奇怪的中国标志)。

在这个例子中,我把字符串的集合如下(注意,字符串不作任何人的感觉,所以不要尝试盘算出来:)):

"[001].[FOO].[TEST] - 'foofoo.test'", 
"[002].[FOO].[TEST] - 'foofoo.test'", 
"[003].[FOO].[TEST] - 'foofoo.test'", 
"[001].[FOO].[TEST] - 'foofoo.test.sample'", 
"[002].[FOO].[TEST] - 'foofoo.test.sample'",  
"-001- BAR.[TEST] - 'bartest.xx1", 
"-002- BAR.[TEST] - 'bartest.xx1" 

现在,我需要的是找到这组字符串的逻辑组(和子组),所以在上面的例子中,通过理性思考,你可以将前3个,后2个和后2个组合起来。从第5,得到的组可以在一个主组与2个亚类,这应该给你这样的事情:

{ 
    { 
     "[001].[FOO].[TEST] - 'foofoo.test'", 
     "[002].[FOO].[TEST] - 'foofoo.test'", 
     "[003].[FOO].[TEST] - 'foofoo.test'", 
    } 
    { 
     "[001].[FOO].[TEST] - 'foofoo.test.sample'", 
     "[002].[FOO].[TEST] - 'foofoo.test.sample'",  
    } 
} 
{ 
    { 
     "-001- BAR.[TEST] - 'bartest.xx1", 
     "-002- BAR.[TEST] - 'bartest.xx1" 
    } 
} 

对不起,上面的布局,但缩进4空格似乎并不正确(或我frakk'n它了)。

无论如何,我不知道如何解决这个问题(如何得到如上所示的结果)。

首先,我想创建一个庞大的正则表达式集,它可以解析大多数已知的模式,但是不同模式的数量只是巨大的,这是不现实的。

另一个想法是解析字符串中的每个单词(所以去除所有非字母或数字字符并拆分),如果X%匹配,我可以假设这些字符串属于同一组。 (其中X可能在80/90左右)。不过,我觉得这个投机领域有点大。例如,当匹配每20个单词的字符串时,击中80%以上的变化有点大(即4个单词可以不同),但是只匹配8个单词时,最多可以有2个单词不同。

我给你的问题是,在上述情况下,什么是合乎逻辑的方法?

至于现实生活中的例子:

提前感谢!

回答

1

大厦@PierrOz的回答,您可以与多种措施进行实验,并做这些措施的统计cluster analysis

例如,你可以使用四项措施:

  1. 多少个字母(大/小写)
  2. 多少位
  3. 有多少([,] ,.)
  4. 如何许多其他字符(可能)没有包含在上面

然后,在这个例子中,每个字符串都有四个度量,如果你愿意,你可以appl y对于每个度量来说是不同的权重。

R具有许多用于聚类分析的功能。 This might be a good starting point


事后反思:这些措施几乎可以是你发明的任何东西。更多示例:

  • 二进制:该字符串是否包含给定字符(0或1)?
  • 二进制:该字符串是否包含给定的子字符串?
  • 计数:给定子字符串出现多少次?
  • 二进制:是否包含字符串全部这些字符?

够了至少周末的修修补补......

+0

欢呼你所有人,这些答案是一个好方法。我会马上开始建立这些概念,谢谢! – Polity 2010-04-03 15:13:14

+0

请稍后再回来让我们知道你是怎么做的! – 2010-04-18 20:56:56

3

基本上我会考虑每个字符串作为一包字符。我将定义两种字符串之间的一种距离,例如“将属于两个字符串的字符数”除以“字符串1中的字符总数+字符串2中的字符总数”。 (好吧,从数学上讲,这不是一个距离......),然后我会尝试将一些算法应用到cluster你的一组字符串中。

嗯,这仅仅是一个基本的想法,但我认为这将是一个良好的开端,尝试一些实验...

1

你的问题是不容易理解,但我想你问什么是不可能做到的以令人满意的方式给予任何一组字符串。这些字符串例如:

[1].[2].[3].[4].[5] 
[a].[2].[3].[4].[5] 
[a].[b].[3].[4].[5] 
[a].[b].[c].[4].[5] 
[a].[b].[c].[d].[5] 
[a].[b].[c].[d].[e] 

每个接近那些上市旁边,所以他们都应该组与他们的邻居,但第一个和最后一个是完全不同的,所以它不会是有意义的组那些在一起。鉴于更多的“分组”数据集,您可能会用PierrOz所描述的方法获得相当好的结果,但不能保证有意义的结果。

我可以打听什么目的是什么?它可以让我们所有人更好地理解什么样的错误是可以容忍的,或者甚至可以用不同的方法来解决问题。

编辑:我不知道,这将是确定的,如果一个字符串在多个不同的组结束了?这可能会使问题变得更简单,并且更可靠地为您提供有用的信息,但您最终会得到一个更大的分组树,并将同一个节点复制到不同分支。

+0

[19720] - [全部] - [#abteevee @ EFnet的] - [Cricket.Highlights.P DTV.XviD-C4TV] - [23/28] - “cricket.highlights。pdtv.xvid-c4tv.vol00 + 01.par2”yEnc(1/3) [19720] - [FULL] - [#abteevee @ EFNet] - [Cricket.Highlights.P DTV.XviD-C4TV] - [18/28] - “cricket.highlights.pdtv.xvid-c4tv.r12”yEnc(1/53) [17537] - [FULL] - [#abteevee @ EFNet] - [ The.Worlds.C4TV] - [01/52] - " sample-the.worlds.c4tv " yEnc(1/15) 前两个字符串属于同一个主组,但都属于它们自己的子组。 – Polity 2010-04-03 13:21:11

+0

更新了原始文章中的结果,因为出现错误,希望它有帮助! – Polity 2010-04-03 13:24:18

1

我会建议使用此:http://en.wikipedia.org/wiki/Hamming_distance的距离。

另外,对于文件一个很好的启发是计算距离之前删除校验和从文件名结尾:

[BSS]_Darker_Than_Black_-_The_Black_Contractor_-_Gaiden_-_01_[35218661].mkv 
-> 
[BSS]_Darker_Than_Black_-_The_Black_Contractor_-_Gaiden_-_01_.mkv 

的检查很简单 - 它总是10个字符,第一个是[,则最后 - ],其余ALPHA-numeric :)

随着启发式和最大距离为4,你的东西将在绝大多数情况下工作。

祝你好运!

+0

海明距离假定输入长度相等,我不能保证这一点。 – Polity 2010-04-03 13:56:46

+0

哦,好吧,不同的长度只是增加了abs(length_2 - length_1):) – glebm 2010-04-03 18:19:28

0

我会忍不住用聚类分析技术来解决这个。点击维基百科进行介绍。其他答案可能属于聚类分析领域,但您可以通过阅读更广泛的内容来找到其他一些有用的方法。