【HSP3】レーベンシュタイン距離を使用した文字列の類似度を調べるモジュール | Codetter（こーどったー）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Wikipediaに記載の擬似コードから変換しています
// http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2
#module
#defcfunc min3 int p1, int p2, int p3
    if p1 > p2{
        if p2 > p3{
            res = p3
        }else{
            res = p2
        }
    }else{
        if p1 > p3{
            res = p3
        }else{
            res = p1
        }
    }
return res
return
#defcfunc LevenshteinDistance str _s1, str _s2
    s1 = _s1 : s2 = _s2
    dim d, strlen(s1)+1, strlen(s2)+1
    i1 = 0 : i2 = 0 : cost = 0
    
    repeat strlen(s1)
        i1 = cnt
        d(i1, 0) = i1
    loop
    
    repeat strlen(s2)
        i2 = cnt
        d(0, i2) = i2
    loop
    
    repeat strlen(s1), 1
        i1 = cnt
        repeat strlen(s2), 1
            i2 = cnt
            if peek(s1, i1) == peek(s2, i2) : cost = 0 : else : cost  =1
            d(i1, i2) = min3( d(i1-1, i2) + 1, d(i1, i2-1) + 1, d(i1-1, i2-1) + cost)
        loop
    loop
        
    
return d(strlen(s1), strlen(s2))
#global
mes LevenshteinDistance("HotSoupProcessor","HotSoupProcessor")
mes LevenshteinDistance("HotSoupProcessor","ColdSoupProcessor")
mes LevenshteinDistance("熱いスープ","冷たいスープ")
mes LevenshteinDistance("オニオン","たまねぎ")
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX