44584


複数の文字列データ同士の組み合わせから、総当たりのレーベンシュタイン距離を計算し、  
最もレーベンシュタイン距離の小さい組み合わせを探そうとしています。

[code]

    # levendist.py
    
    import numpy as np
    def levenshtein(source, target):
        if len(source) < len(target):
            return levenshtein(target, source)
    
        # So now we have len(source) >= len(target).
        if len(target) == 0:
            return len(source)
    
        # We call tuple() to force strings to be used as sequences
        # ('c', 'a', 't', 's') - numpy uses them as values by default.
        source = np.array(tuple(source))
        target = np.array(tuple(target))
    
        # We use a dynamic programming algorithm, but with the
        # added optimization that we only need the last two rows
        # of the matrix.
        previous_row = np.arange(target.size + 1)
        for s in source:
            # Insertion (target grows longer than source):
            current_row = previous_row + 1
    
            # Substitution or matching:
            # Target and source items are aligned, and either
            # are different (cost of 1), or are the same (cost of 0).
            current_row[1:] = np.minimum(
                    current_row[1:],
                    np.add(previous_row[:-1], target != s))
    
            # Deletion (target grows shorter than source):
            current_row[1:] = np.minimum(
                    current_row[1:],
                    current_row[0:-1] + 1)
    
            previous_row = current_row
    
        return previous_row[-1]
    
[/code]

上のモジュールでlevenshteinを定義して、  
下で2つの文字列配列を総当たりで調べようとしています。

[code]

    ValueError: could not broadcast input array from shape (2,2) into shape(2)
    
[/code]

と出てしまいます。

[code]

    import numpy as np
    import levendist as leven
    
    lst1 = np.array([[1],[2]])
    lst2 = np.array([3,4,5,6,7,8,9])
    #print(lst1.shape)
    #print(lst2.shape)
    
    lst3=leven.levenshtein(lst1,lst2)
    
    print(lst3.shape)
    print(lst3)
    
    print(np.max(lst3, axis = 1))
    lst4 = np.max(lst3, axis = 1)
    print(lst4.shape)
    
[/code]

Llevenshteinでsourceとtargetを入れ替えているからかもしれませんが、どのようにかして総当たりのレーベンシュタイン距離を求められないでしょう。


CC BY-SA 3.0
2017-03-26T10:51:38.420
33551
2018-06-07T11:50:24.187
2017-03-31T08:30:20.710
3054
21201
question
python
総当たりレーベンシュタイン距離


`lst1`と`lst2`の形が異なっていたため、flatten
して普通のリストにして、2重のfor文で総当たりで`levendist`の結果を出力し、`lst1`の要素数x`lst2`の要素数の2次元配列（行列？）にそれらを入れた後最小の要素を見つけました。

[code]

    import levendist as leven
    import numpy as np
    
    lst1 = np.array([["abc"], ["def"]])
    # 文字列の配列に
    lst1 = lst1.flatten()
    lst2 = np.array(["ab", "cdef", "ghijk", "lmn"])
    
    levs = np.zeros( (lst1.size, lst2.size), dtype=np.int)
    for i, elm1 in enumerate(lst1):
        for ii, elm2 in enumerate(lst2):
            levs[i, ii] = leven.levenshtein(elm1, elm2)
    
    print("# レーベンシュタイン距離が最小の組合せ")
    min_lev = levs.min()
    print("距離:", min_lev)
    print("組み合せ:")
    for i in np.argwhere(levs == min_lev):
        print("   ", lst1[i[0]], lst2[i[1]])
    
[/code]

出力:

[code]

    # レーベンシュタイン距離が最小の組合せ
    距離: 1
    組み合せ:
        abc ab
        def cdef
    
[/code]

\-- この回答は、[質問者さん](https://ja.stackoverflow.com/users/21201/kojiro-
ikeda)の[コメント](https://ja.stackoverflow.com/questions/33551/%E7%B7%8F%E5%BD%93%E3%81%9F%E3%82%8A%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#comment33397_33551)を元に推測も含め編集したものです。


CC BY-SA 4.0
2018-06-07T05:33:59.893
44584
2018-06-07T11:50:24.187
2018-06-07T11:50:24.187
3054
19110
33551
answer