Julia言語で二つの文字列の最長一致した文字列を抽出(Rosetta Codeからのパクり)

仕事で必要になるかと思って，調べていて結局使わなかった内容なのですが， 一応日記に残しておきます。

二つの文字列で，共通する連続した最長の部分文字列を抽出するというものです。

色々ネットで探していると， Rosetta Codeというサイトに Longest common substring(Julia)という内容でありました。

次のような内容です。

# https://rosettacode.org/wiki/Longest_common_substring#Julia から引用

function lcs(s1::AbstractString, s2::AbstractString)::String
    l, r, sub_len = 1, 0, 0
    for i in eachindex(s1)
        for j in i:length(s1)
            contains(s2, SubString(s1, i, j)) || break
            if sub_len ≤ j - i
                l, r = i, j
                sub_len = j - i
            end
        end
    end 
    return s1[l:r] 
end

@show lcs("thisisatest", "testing123testing")

実行結果は次の通りです。

julia> include("lcs.jl")
lcs("thisisatest", "testing123testing") = "test"
"test"

しかし，予想通りというか日本語等のマルチバイト文字には対応していません。 次は実行がうまくいかない例です。

julia> lcs("そして日本語入力は", "悲しき日本語処理の話")
ERROR: StringIndexError: invalid index [5], valid nearby indices [4]=>'し', [7]=>'て'
Stacktrace:
 [1] string_index_err(s::String, i::Int64)
   @ Base ./strings/string.jl:12
 [2] SubString{String}(s::String, i::Int64, j::Int64)
   @ Base ./strings/substring.jl:35
 [3] SubString
   @ ./strings/substring.jl:49 [inlined]
 [4] lcs(s1::String, s2::String)
   @ Main ~/blog/test/lcs.jl:5
 [5] top-level scope
   @ REPL[36]:1

そこで，少し改造してマルチバイト文字にも対応させます。改造例は次の通りです。

function lcs(s1::AbstractString, s2::AbstractString)::String
    l, r, sub_len = 1, 0, 0
    k1, len_s1 = [k for k in eachindex(s1)], length(s1)
    for i in 1:len_s1
        for j in i:len_s1
            contains(s2, SubString(s1, k1[i], k1[j])) || break
            if sub_len ≤ j - i
                l, r, sub_len = i, j, j - i
            end
        end
    end 
    return s1[k1[l]:k1[r]] 
end

eachindex(s1)であらかじめ文字の先頭インデックスを求めておいて， インデックス指定する時にその値を使うというものです。

次が実行例です。同じ文字数の時は，一つ目の文字列の後で見つけたものが優先するようです。 この動作は if sub_len ≤ j - i の ≤ を < とすることで変更することができそうです。

julia> include("lcs-utf.jl")
lcs (generic function with 1 method)

julia> lcs("そして日本語入力は", "悲しき日本語処理の話")
"日本語"

julia> lcs("漢直という日本語入力は…", "悲しき日本語処理の話")
"日本語"

julia> lcs("漢直という日本語入力は悲しき運命を辿る…", "悲しき日本語処理の物語")
"悲しき"

Rosetta CodeのJulia言語のカテゴリ のページにはいくつもの実装例があるようです。

また，同じ内容を実現する他のプログラム言語の実装例とも比較でき， 自分で一から実装することをほとんどしない自分にとっては，今後も参考にできそうです。