是可能的組串的基礎上在紅寶石相似度

我已經實現這些基團類似使用文本環路定製紅寶石方法的陣列，是可能的組串的基礎上在紅寶石相似度

array = ["South East Queensland", "Wide Bay Burnett", "Margaret River", "Port Pirie", "Gippsland", "Elizabeth", "Barossa"] 
similarity_group = [] 
similarity_percentage = 60.0 

array.each do |first_text| 
    results.each do |second_text| 
    result = first_text.upcase.similar(second_text.upcase) 
    if result >= similarity_percentage 
     ... 
     ... 
     ... 
    end 
    end 
end

考慮上述實施2000元件，然後以組他們將花費4000000次迭代，因爲每個元素都會互相檢查。

是否有任何高性能解決方案或寶石或庫，如基於它們的相似性來分組批量數組。

（我需要使用的相似性檢查相同的數組元素）

樣的期望：[array1].similarity([array1])

來源

2017-01-30 Ferdinand Rosario

'similar'從哪裏來？它來自寶石嗎？哪一個？ –

注意：您可以使用'first_text'兩次。我認爲相似性總是1 :)一個明顯的優化是隻有在'string1> = string2'時才檢查2個字符串。它將迭代減半。 –

我想你基於字符串的距離（例如Levensthein）尋找clustering。從你的代碼看，similar看起來已經實現了，所以它必須清楚你正在考慮的距離。

對於羣集，這些two gems可能有所幫助。

雖然問題是hard，所以你的O（n ** 2）實際上並沒有那麼差。在計算距離之前，只需檢查string1 > string2即可避免兩次比較字符串對。您需要(2000*1999)/2迭代而不是2000**2。

來源

2017-01-30 14:07:10

謝謝@Eric Duminil，是的類似的是一個寶石，它有助於找到兩個字符串之間的相似性百分比。抱歉，這是一個錯字。我更新了我的問題。 –

我有一個矩陣解我過去用來比較電子書，因爲這些都是相當大的，需要時間來處理我用矩陣解決了這個問題，後來我用一個索引導出了一個值從那些精確和快得多的書中。我可以爲你搜索矩陣解決方案，但是我有另一個基於levenshtein的簡單例程，它看起來像你想要完成的，創建一個相似性數組（這裏是一個哈希）。

我發佈了我的腳本的工作版本，就像我的腳本庫一樣，所以你可能會想要修改它的一部分。我以前在this問題上用它作爲答案。你可以例如以相同的方式構建一個數組。

require 'levenshtein' 

MAX_DISTANCE, COMPENSATION = 3, 5 

strings = [ 
    "Hazard Const. Company", 
    "hazard construction company", 
    "PETERSON-CHASE GENERAL ENGINEERING CONSTRUCTION INC", 
    "peterson-chase general engineering construction inc", 
    "TRAFFIC DEVELOPMENT SERVICES ", 
    "traffic development services" 
] 

result = {} 
strings.each do |s| 
    s.downcase! 
    similar = result.keys.select { |key| Levenshtein.distance(key, s) < MAX_DISTANCE+(s.length/COMPENSATION) } 
    if similar.any? 
    result[similar.first] += 1 
    else 
    result.merge!({s => 1}) 
    end 
end 

p result 
# {"hazard const. company"=>2, "peterson-chase general engineering construction inc"=>2, "traffic development services "=>2}

來源

2017-01-30 17:17:47 peter

非常感謝您和@Eric Duminil。讓我試試你的兩個解決方案。 –

是可能的組串的基礎上在紅寶石相似度

回答

相關問題