2010-04-03 40 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

我會忍不住用聚類分析技術來解決這個。點擊維基百科進行介紹。其他答案可能屬於聚類分析領域,但您可以通過閱讀更廣泛的內容來找到其他一些有用的方法。