有序連續的文本匹配

我想匹配的字符串，並通過以下方式獲得的分數，有序連續的文本匹配

string 1: 4556677, string 2: 2556677, score: 0 
    string 1: 123345873009, string 2: 123345873112, score: 9 
    string 1: 22334567, string 2: 22334500, score: 6

這樣的比分代表常見的前n位，由左到右。

我有一個100K字符串1和30M字符串2的列表，我想用大於'x'的分數來過濾所有對（字符串1和2）。

有沒有一種算法可以完成這個任務而不是殘酷的力量順序匹配？我有表存儲在Apache配置單元/ hbase中，並希望在spark或java mapreduce中實現該方法。任何幫助深表感謝。

來源

2016-08-02 Mike

我得出結論，你的「分數」表示字符串不同的最左邊的字符位置。

沒關係「mapreduce」，簡單的簡Java可以很容易地做到這一點。

公衆詮釋得分（字符串字符串1，字符串字符串2）{
炭SBUF1 [] = string1.toCharArray（）;
char sbuf2 [] = string2.toCharArray（）;

int complen = sbuf1.length;

如果（sbuf2.length < complen）{
complen = sbuf2.length;
}
爲（ INT I = 0;我< complen;我++）{
如果（SBUF1 [I]！= SBUF2 [I]）{
返回 I;
}
}
返回-1; // 表示沒有檢測到不匹配前一個字符串用盡
}

來源

2016-08-02 14:44:22

欣賞這個您能撥冗。但是這是一對一的比較，這會使對的數量被檢查爲'100k * 30M'，即使考慮消除不共享相同的第一位數字的對，效率也不高。我需要知道是否有任何數據結構（樹狀）可以適應這種匹配的快速實現。 – Mike

有序連續的文本匹配

回答

相關問題