iT邦幫忙

1

尋找字串 找到最長重複的字串,我有使用suffix_trees 跟網路上的一些code

'hellowdfbvsfbsdbsdhellowscssdthavcscsdrssbhellowmf'
答案是hellow

但並不是我要的答案請問有比較適合的方法例如from suffix_trees import STrees 的Python也適用的演算法嗎?
可以指點我一下嗎 拜託了!!

看更多先前的討論...收起先前的討論...
slime iT邦大師 1 級 ‧ 2018-06-28 09:04:20 檢舉
先說說看你想要的答案是什麼?
再分析看看你要的答案是依怎樣的特徵找到的?
再比對程式內的寫法是否符合這特徵的找法.
hoolada iT邦新手 5 級 ‧ 2018-06-28 14:51:29 檢舉
我要的答案最長重複字串
依分群出來的值,每一個執會顯示分群後屬於哪個群我把它當作字串
{1,5,6,7,5,2,8,9,4,5,6,7,5,2,8,9,4,4,2,2,6,6,9,5,3,1,0,7,5,2,6,5,4,4,2,3,6,8,4}
他印出來就會是這個答案5,6,7,5,2,8,9最長的字串
再比對程式內的寫法是否符合這特徵的找法 這是說suffix_trees 其實是可以做到的 但我只用了他pip 的範例做嘗試 所以拿不到我要的答案嗎?
slime iT邦大師 1 級 ‧ 2018-06-28 15:20:02 檢舉
更不懂了....

最長重複字串的定義是?
分群的分法?
suffix_trees程式的來源?
pip?
hoolada iT邦新手 5 級 ‧ 2018-06-28 16:00:17 檢舉
定義 是要找一個規則 我的想法把它變成字串 找到一個最長重複字串
{1,5,6,7,5,2,8,9,4,5,6,7,5,2,8,9,4,4,2,2,6,6,9,5,3,1,0,7,5,2,6,5,4,4,2,3,6,8,4}這是個例子
這例子最長重複字串5,6,7,5,2,8,9 這字串
分群 C-means K-means 都有做
https://pypi.org/project/suffix-trees/
我在想他的意思是指.. 一列有規則順序長字串, 當中可能有一組最長的重覆字串, 他要把它找出來.
如: ABCD Z ABCD Y ABC W AB .. 則最長重覆字串,就是ABCD
hoolada iT邦新手 5 級 ‧ 2018-06-29 15:56:59 檢舉
對 但我之前沒有打好 我的字串沒有空格跟,
他長這樣 例如
'1123364113511311234561234565225497123456'
fysh711426 iT邦研究生 4 級 ‧ 2018-06-30 22:16:35 檢舉
小弟有個疑問
{1,5,6,7,5,2,8,9,4,5,6,7,5,2,8,9,4,4,2,2,6,6,9,5,3,1,0,7,5,2,6,5,4,4,2,3,6,8,4}
的最長子字串為什麼是
5,6,7,5,2,8,9
而不是
5,6,7,5,2,8,9,4
呢?
hoolada iT邦新手 5 級 ‧ 2018-07-01 08:15:50 檢舉
你是對的 我打錯 哈哈SORRY!

1 個回答

1
fysh711426
iT邦研究生 4 級 ‧ 2018-07-01 04:16:29
最佳解答

蠻有趣的,研究了好一陣子,寫了一個擴充方法,給您看看是不是您需要的。
/images/emoticon/emoticon37.gif

首先 Google 了 suffix-trees,發現這是個後綴樹演算法的實作,
後綴樹!!! 沒聽過的新名詞,這勾起了小弟我的興趣,
繼續 Google 找到了這篇文章 后缀树
且在最後 后缀树的应用 找到了大大的需求。

  • 查找字符串 Text 中的最长重复子串
    說明: 用 Text+'$' 建立後綴樹,搜尋最深的非葉節點,從根結點到到該節點所經過的字串就是最長重複子字串。

詳細原理文章內寫得很清楚,有興趣的大大可以點進去看看。

了解原理後就可以進入程式碼的部分,
看完 suffix_trees 的原始碼,發現並沒有查詢 最長重複子字串 的功能,
不過有個類似的方法 lcs(),可以查詢多個字串的最長共用部分,
既然有現成的,那就以此為基礎修改成我們想要的。

我將這個擴充方法獨立一個檔案 suffix_trees_ex.py,主程式需要再 import 就好。
程式碼:

class STreeEx():
    def __init__(self, sTree):
        # 傳入原套件後綴樹
        self.sTree = sTree

    def lrs(self):
        # 最深非葉節點
        deepestNode = self._find_lrs(self.sTree.root)
        start = deepestNode.idx
        end = deepestNode.idx + deepestNode.depth
        return self.sTree.word[start:end]

    def _find_lrs(self, node):
        nodes = [self._find_lrs(n)
            for (n,_) in node.transition_links
            # 排除葉節點
            if n.transition_links != []]

        if nodes == []:
            return node
        
        deepestNode = max(nodes, key=lambda n: n.depth)
        return deepestNode

主程式:

from suffix_trees import STree
from suffix_trees_ex import STreeEx

st = STree.STree("156752894567528944226695310752654423684")
st = STreeEx(st)

print(st.lrs())   # 56752894

最後附上一張小弟研究 suffix_trees 內部結構時畫的圖,和上面文章的 Compressed Trie 比對會更清楚。

https://ithelp.ithome.com.tw/upload/images/20180701/20106865UEntxQzrJ0.jpg

看更多先前的回應...收起先前的回應...
hoolada iT邦新手 5 級 ‧ 2018-07-01 08:16:03 檢舉

超級詳解!

超級無敵詳解!
大大的研究精神完全爆表XD

fysh711426 iT邦研究生 4 級 ‧ 2018-07-01 21:17:57 檢舉

hoolada 哈哈哈,感謝大大的問題,我對 Python 和深度學習蠻有興趣的。
/images/emoticon/emoticon37.gif


補充一下,最長重複子字串,有分兩種,以 banana 為例:

  1. 可重疊 -> ana
  2. 不可重疊 -> anna

我上面的做法是 可重疊 的解,
另外還有一個可以改善的地方,目前如果有多個解,只會回傳最先找到的那個解。

參考資料:
最长重复子串和最长不重复子串求解
演算法筆記

fysh711426 iT邦研究生 4 級 ‧ 2018-07-01 21:22:31 檢舉

神Q超人 哈哈哈,謝謝大大,話說您這禮拜的題目,小弟還在苦等中。
/images/emoticon/emoticon02.gif

哈哈哈,這週末有點忙,所以在禮拜天的尾巴生出來了XD
謝謝大大一直支持!
今天晚上就好好休息吧!明天再看,哈哈哈。

我要發表回答

立即登入回答