Fw: [問題] 兩串數字的模糊比對的演算法怎麼寫??

[yhn0tgb60 (呦厚厚)]

※ [本文轉錄自 C_and_CPP 看板 #1F02pD61 ]

作者: yhn0tgb60 (呦厚厚) 看板: C_and_CPP
標題: [問題] 兩串數字的模糊比對的演算法怎麼寫??
時間: Sun Jan  1 17:52:10 2012

就是我要作兩串數字的模糊比對


假如兩串數字是

3,    2, 8

3, 1, 2, 8, 9, 0


程式會知道

第二串比第一串多了 1, 9, 0 這三個數字

這種數字比較多的狀況還好判斷

只要跑迴圈以第一串數字作基準去與第二串數字作比較就好了



假如如果是

3, 2, 9

3, 1, 9

那就是 程式要知道這兩串數字是 2, 1 的差別

也不難,  就一個一個拿出來比較好了




可是如果是兩種狀況混合呢???


3,  2,  9     , 7

    1,  9 , 0 , 7 , 4


程式要如何知道

第二串比第一串 少了 3  多了 0, 4   而 2 和 1  不同??


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.155.241
→ EdisonX:為什麼會判別到 2,1 不同？而不是第一串少1,第二串少2 ?
推 ericinttu:這應該無關"模糊"二字
其實這是目前的狀況, 未來會由 user輸入數字, 去跟一堆的數字串相比,

看使用者輸入的和哪一個字串相似度最高

→ yinbunbun:聽起來像是Longest Common Sequence的變型
※ 編輯: yhn0tgb60       來自: 122.116.155.241      (01/01 18:36)
推 yoco315:http://en.wikipedia.org/wiki/Edit_distance
→ loveme00835:跟程式語言實作無關者請轉至Prob_Solve，轉錄後刪原文
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: yhn0tgb60 (122.116.155.241), 時間: 01/01/2012 18:53:30
→ tkcn:1f, 3f 已經給你很好的建議了
推 yauhh:這種問題,一般認定為文件相似度的識別. 有一種處理法是用
→ yauhh:貝式機率/頻率方式幫助判斷.
→ yhn0tgb60:謝謝拉