-1

この質問は、画像処理におけるパターン マッチングに近いかもしれません。

リスト間の近接性を返す、異なるリストに適用されるコスト関数値を取得する方法はありますか? 例えば、

a = [4, 7, 9]
b = [5, 8, 10]
c = [2, 3]

ここで、のコスト関数値は 2 タプルである可能性があり、(a, b) は (a, c) および (b, c) より大きくなければなりません。リストの数がさらに多くなる可能性があり、すべての順列が問題の複雑さを爆破する可能性があるため、これは巨大な計算タスクになる可能性があります。したがって、2タプルのセットのみが機能します。

編集: リスト名はアクションのタイプを示し、それらの要素は対応するアクションが発生する時間を示します。私がやろうとしているのは、同様の発生パターンを持つアクションのセットを考え出すことです。2 つのアクションが同時に発生することはないため、リスト内距離とリスト間距離の組み合わせになります。

前もって感謝します！

4

3 に答える 3

0

2つの文字列またはリストを比較するには、レーベンシュタイン距離を使用できます（ここからのPython実装）。

def levenshtein(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
        matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
        for sz in range(0,l1):
            if s1[sz] == s2[zz]:
                matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, 
                                         matrix[zz][sz+1] + 1, 
                                         matrix[zz][sz])
            else:
                matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, 
                                         matrix[zz][sz+1] + 1, 
                                         matrix[zz][sz] + 1)
    return matrix[l2][l1]

あなたのリストでそれを使用する：

>>> a = [4, 7, 9]
>>> b = [5, 8, 10]
>>> c = [2, 3]
>>> levenshtein(a,b)
3
>>> levenshtein(b,c)
3
>>> levenshtein(a,c)
3

編集set：コメントに説明を追加すると、リストの代わりにsを使用できます。セットのすべての要素は一意であるため、既存の要素を再度追加することはできません。また、セットのisdisjointメソッドを使用して、2つのセットに同じ要素が含まれていないことを確認したり、intersectionメソッドを使用して、それらに共通する要素が含まれていないことを確認したりできます。

In [1]: a = {1,3,5}

In [2]: a.add(3)

In [3]: a
Out[3]: set([1, 3, 5])

In [4]: a.add(4)

In [5]: a
Out[5]: set([1, 3, 4, 5])

In [6]: b = {2,3,7}
In [7]: a.isdisjoint(b)
Out[7]: False

In [8]: a.intersection(b)
Out[8]: set([3])

注意：セットを作成するこの構文には、少なくともPython2.7が必要です。

于 2012-08-15T08:25:45.070 に答える
0

あなたは非常に難しい質問をしています。サイズを変更することを許可しなくても、使用できるいくつかの距離尺度が既に存在します (ユークリッド、マンハッタンなど。詳細については「関連項目」セクションを確認してください)。必要なものは、これらのリストが何を表しているとしても、近接性の適切な尺度と思われるものによって異なります。

これらのリストで何をしようとしているのかを知らなければ、それを効率的に計算する方法は言うまでもなく、良い答えが何であるかを誰も定義できません。

于 2012-08-15T08:37:29.903 に答える
0

マイケルの説明に対するあなたの答えを考えると、おそらく「Dynamic Time Warping」を調べる必要があります。

私はhttp://mlpy.sourceforge.net/を使用していませんが、その宣伝文句には DTW を提供すると書かれています。(ナットを割るためのハンマーかもしれません。ユースケースによって異なります。)

于 2012-08-15T11:56:49.403 に答える