如何基於給定的線S和模式的列表L模式

列表[L ，...，L _ñ]上記號化條紋字符串，你會如何找到所有憑證清單在S中匹配L中的模式並且使得S中匹配字母的總數最大化？如何基於給定的線S和模式的列表L模式

一個虛擬的例子是S =「thenuke」，L = {「the」，「then」，「nuke」}，我們想檢索[「the」，「nuke」]，就像我們開始匹配「那麼」，我們沒有得到最大化匹配的S中字母總數的解決方案。

我一直在看其他SO問題，string matching algorithms，但沒有找到有效解決問題的最大化部分。這一定是研究過的，例如在生物信息學，但我不在現場，所以任何幫助（包括鏈接到學術論文）深表感謝！（| L || S |）

來源

2012-09-11 marchelbling

爲每一次嘗試保留一個計數器，然後找到最佳匹配？就像運行''''一樣，如果你能找到'nuke'，返回2，然後運行'then'並立即返回1，以便立即檢查1是否較大，顯然不是並且保持前一個是最大值。 ..並繼續做下去，直到你完成！ –

此最佳匹配可以在O解決（| S | + | L | + k）的時間，其中k是從L的S.所有串的匹配的總數有兩個主要步驟：

運行Aho-Corasick。這會給你所有來自S的字符串的匹配。這與上面提到的相同。
初始化一個數組A，長度爲整數| S | +1全部爲零。3月通過陣列，在位置i我設置A [i]爲A [i-1]（如果它較大），則對於每個匹配，M，從位於第i個位置的S中的L開始，將A [i + | M |]設置爲A [i + | M |]和A [i] + | M |的最大值。

下面是Go中的一些代碼，完全是這樣。它使用我寫的一個包裝，它有一個方便的包裝來呼叫Aho-Corasick。

package main 

import (
    "fmt" 
    "github.com/runningwild/stringz" 
) 

func main() { 
    input := []byte("thenuke") 
    patterns := [][]byte{[]byte("hen"), []byte("thenu"), []byte("uke")} 

    // This runs Aho-Corasick on the input string and patterns, it returns a 
    // map, matches, such that matches[i] is a list of indices into input where 
    // patterns[i] matches the input string. The running time of this is 
    // O(|input| + |patterns| + k) and uses O(|patterns| + k) auxillary storage, 
    // where k is the total number of matches found. 
    find := stringz.FindSet(patterns) 
    matches := find.In(input) 

    // We want to invert the map so that it maps from index to all strings that 
    // match at that index. 
    at_pos := make([][]int, len(input)+1) 
    for index, hits := range matches { 
    for _, hit := range hits { 
     at_pos[hit] = append(at_pos[hit], index) 
    } 
    } 

    // Now we do a single pass through the string, at every position we will 
    // keep track of how many characters in the input string we can match up to 
    // that point. 
    max := make([]int, len(input)+1) 
    for i := range max { 
    // If this position isn't as good as the previous position, then we'll use 
    // the previous position. It just means that there is a character that we 
    // were unable to match anything to. 
    if i > 0 && max[i-1] > max[i] { 
     max[i] = max[i-1] 
    } 

    // Look through any string that matches at this position, if its length is 
    // L, then L positions later in the string we can have matched L more 
    // character if we use this string now. This might mean that we don't use 
    // another string that earlier we thought we'd be matching right now, we'll 
    // find out later which one was better. 
    for _, hit := range at_pos[i] { 
     L := len(patterns[hit]) 
     if i+L < len(max) && max[i+L] < max[i]+L { 
     max[i+L] = max[i] + L 
     } 
    } 
    } 

    fmt.Printf("%v\n", max) 
}

來源

2012-09-11 23:06:38

+1。我在[這個答案]中寫了這個算法的Python實現（http://stackoverflow.com/a/12404740/68063）。 –

可以在時間爲O解決這個由dynamic programming：建立一個迭代表給出最佳匹配的S = s各自初始子小號內容S _ñ：

B（0），對於S的零長度初始子的最佳匹配，是空的匹配。
假設我們已經計算出的最佳匹配，B（我），每個我 < ķ，我們現在要計算B（ķ）。假設p是L中的模式， p |，並讓j = k - | p | + 1。如果p = S _Ĵ內容S _ķ然後存在匹配對於s 小號內容S _ķ，其由B的（j），然後是p。令B（ķ）是考慮所有的模式中L.
B（Ñ）後發現的最好的這樣的匹配是針對整個S.
的

來源

2012-09-11 22:25:07

如何基於給定的線S和模式的列表L模式

回答

相關問題