スポンサーサイト

    上記の広告は1ヶ月以上更新のないブログに表示されています。
    新しい記事を書く事で広告が消せます。

    テキストの内容を比較するアルゴリズム

    diffツールでおなじみの二つのテキストの内容を比較するアルゴリズム,おもしろそうだと思いつつ難しいんだろうなと漠然と思っていて今まで調べることがなかったのですが,近いうちにちょっと必要になりそうだったのでどんなものかと思って今週少し調べたりしていました.

    以下の記事が検索で出てくる,アルゴリズムの良い解説記事なのですが(記事の作成者の方に感謝),それでも最初見たときはすぐに理解できなかったりしました.

    http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
    http://www.slash-zero.jp/archives/program/466

    だんだん飲み込めてくるとそのアルゴリズムのシンプルさがじわじわわかってきて,実際に処理を組んでみると実装もかなりきれいにまとまって,シンプルかつ効率的なアルゴリズムで感心しました.上記記事の説明と元の論文の実装例を見るのが理解しやすいかもです.とはいえ,他人に説明できるほどには理解できていない感じなのですが・・・


    ソースコードは最後に付けますが,使い方は以下のような感じ(Util.Differenceが比較クラス/VB.NETで実装).

    文字単位比較の場合
        <TestMethod()> Public Sub T002_UtilTestテキスト差分()
    Dim a = "123ABCDEFGGFDES"
    Dim b = "456ABCDEFssGGSFDES"

    Dim dm As New Util.Difference(Of Char)(a, b)
    Dim sed = dm.Compare()

    DisplayDifferences(Of Char)(sed, a, b)
    End Sub


    行単位比較の場合
        <TestMethod()> Public Sub T003_UtilTestテキスト差分()
    Dim a = {" ' 指定の斜め線のY位置から一致終了の点までを探索",
    " Private Function Snake(k As Integer, y As Integer) As Integer",
    " Dim x = y - k",
    " 'Debug.Write(String.Format(""{2} : ({0}, {1}) - "", x, y, k))",
    " While x < _a.Length And y < _b.Length AndAlso _a(x).Equals(_b(y))",
    " y += 1",
    " End While",
    " Debug.WriteLine(String.Format(""({0}, {1})"", x, y))",
    " Return yyyyyyyyyy",
    " End Function"}
    Dim b = {" ' 指定の斜め線のY位置から一致終了の点までを探索",
    " Private Function Snake(k As Integer, y As Integer) As Integer",
    " Dim x = y - k",
    " 'Debug.Write(String.Format(""{2} : ({0}, {1}) - "", x, y, k))",
    " While x < _a.Length And y < _b.Length AndAlso _a(x).Equals(_b(y))",
    " x += 1",
    " End While",
    " Debug.WriteLine(String.Format(""({0}, {1})"", x, y))",
    " Return y",
    " End Function"}

    Dim dm As New Util.Difference(Of String)(a, b)
    Dim sed = dm.Compare()

    DisplayDifferences(Of String)(sed, a, b)
    End Sub


    上のソースで使っている結果表示の処理は以下のとおりです
        ' 差分を表示
    Private Sub DisplayDifferences(Of T)(sed As Tuple(Of Integer, Integer)(), a As T(), b As T())
    Dim ind1 As Integer = 0
    Dim ind2 As Integer = 0
    For i As Integer = 0 To sed.Length - 1
    If ind1 <> sed(i).Item1 And ind2 <> sed(i).Item2 Then
    ' 一致部分
    For j = 0 To sed(i).Item1 - ind1 - 1
    Debug.WriteLine(String.Format("{0}{2}{1}", a(ind1 + j), b(ind2 + j), vbTab))
    Next
    ElseIf ind1 <> sed(i).Item1 Then
    ' aにだけある部分
    For j = 0 To sed(i).Item1 - ind1 - 1
    Debug.WriteLine(String.Format("{0}{2}{1}", a(ind1 + j), String.Empty, vbTab))
    Next
    Else ' If in2 <> ss(i).Item2 Then
    ' bにだけある部分
    For j = 0 To sed(i).Item2 - ind2 - 1
    Debug.WriteLine(String.Format("{0}{2}{1}", String.Empty, b(ind2 + j), vbTab))
    Next
    End If
    ind1 = sed(i).Item1
    ind2 = sed(i).Item2
    'Debug.WriteLine(String.Format("({0}, {1})", ii.Item1, ii.Item2))
    Next
    End Sub


    比較したい単位を型パラメータで渡せばその単位で差分を取ります(Byteを型パラメータにすれば多分バイナリもいけるはず.Compare関数が実装されていればオッケー).上の例では指定していませんが,比較対象がほとんど一致しない場合にはメモリを大量に消費することになるので,コンストラクタで差分の比較の打ち切り閾値を指定できるようにしています.比較する対象に一致がほとんどない場合は比較そのものにあまり意味がないので,ほどほどで打ち切るように設定するのが良いかもしれません.

    ついでなので,このアルゴリズムを使って作成されるエディットグラフを視覚的に表示する簡単なアプリを作ってみました.Silverlightプラグインをインストールする必要がありますがよろしければこちらからどうぞ.画面上部の二つのテキストボックスに入力したテキストのエディットグラフを表示します.そこそこ似ていてそこそこ違う文字列を入れるとおもしろいかもしれません.


    以下が実装したクラスのソース(VB.NET).エディットグラフを作る処理が入っているのでオリジナルのアルゴリズムの美しさが少し崩れていてアレですが・・・
    ' 2つの配列間の最短編集経路を作成
    Public Class Difference(Of T)

    ' 編集経路記録用グラフ
    Private ReadOnly _graph As New Dictionary(Of Tuple(Of Integer, Integer), List(Of Tuple(Of Integer, Integer)))
    Private ReadOnly _parentMap As New Dictionary(Of Tuple(Of Integer, Integer), Tuple(Of Integer, Integer))

    ' 比較対象配列
    Private ReadOnly _a As T()
    Private ReadOnly _b As T()

    ' 無編集で到達できる最大Y深度
    Private ReadOnly _fp As MyArray

    ' 差分探索の打ち切りしきい値
    Private ReadOnly _threshold As Integer

    ' 文字列の長さの差(編集回数の最小値)
    Private ReadOnly Property DELTA As Integer
    Get
    Return _b.Length - _a.Length
    End Get
    End Property

    ' コンストラクタ
    Public Sub New(A As T(), B As T(), Optional threshold As Integer = 0)
    ' 短い方をA,長い方をBに設定
    If A.Length <= B.Length Then
    _a = A
    _b = B
    Else
    _a = B
    _b = A
    End If
    Debug.Assert(0 <= DELTA)
    _fp = New MyArray(-(_a.Length + 1), _b.Length + 1)
    _threshold = threshold
    End Sub

    '[1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266
    '[2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparison Algorithm", August 1989
    ' O(NP)アルゴリズム.エディットグラフ上のSEDパスを返却
    Public Function Compare() As Tuple(Of Integer, Integer)()
    _fp.Initialize()
    _graph.Clear()
    _parentMap.Clear()

    Dim p As Integer = 0
    Do
    ' 左側から⊿線
    For k As Integer = -p To DELTA - 1
    FindPath(k)
    Next
    ' 右側から⊿線
    For k As Integer = DELTA + p To DELTA + 1 Step -1
    FindPath(k)
    Next
    ' ⊿線
    FindPath(DELTA)
    If _fp.Item(DELTA) = _b.Length Then Exit Do ' 探索終了
    p += 1
    Loop

    Debug.WriteLine("the edit distance is {0}", DELTA + 2 * p)

    ' 作成したツリーを末尾から辿ってSEDを作成
    Dim s As New Stack(Of Tuple(Of Integer, Integer))
    Dim current = MakeKey(_a.Length, _b.Length)
    Do
    s.Push(current)
    If current.Item1 = 0 Or current.Item2 = 0 Then Exit Do
    current = _parentMap(current)
    Loop
    Return s.ToArray
    End Function

    ' 編集経路探索
    Private Sub FindPath(k As Integer)
    Dim y = Math.Max(_fp.Item(k - 1) + 1, _fp.Item(k + 1))
    Dim k1 = 0
    ' 隣の斜線上の交点からYの深い方を選択
    ' (グラフ上の経路は上から下,左から右にしか移動できないので,左の線からはY+1(→),右の斜線からはY(↓)で移動できる点に注意(※横軸がY,縦がX))
    If _fp.Item(k - 1) + 1 >= _fp.Item(k + 1) Then
    k1 = k - 1
    Else
    k1 = k + 1
    End If
    ' 選択した交点(n1)とその点から横か下に移動した交点(n2)との経路を記録
    Dim y1 = _fp.Item(k1)
    Dim n1 = MakeKey(y1 - k1, y1)
    Dim n2 = MakeKey(y - k, y)
    AddChild(n1, n2)

    ' n2から斜めに移動できる点(一致部分)を探索
    _fp.Item(k) = Snake(k, y)
    Dim ny = _fp.Item(k)
    If ny > y Then
    ' 斜めに移動できたらn2から移動した点(n3)までの経路を記録
    Dim n3 = MakeKey(ny - k, ny)
    AddChild(n2, n3)
    MakeNode(n3)
    End If
    End Sub

    ' キー作成
    Private Function MakeKey(x As Integer, y As Integer)
    Return New Tuple(Of Integer, Integer)(x, y)
    End Function

    ' 節点作成
    Private Sub MakeNode(n As Tuple(Of Integer, Integer))
    If Not _graph.ContainsKey(n) Then _graph.Add(n, New List(Of Tuple(Of Integer, Integer)))
    If 0 < _threshold AndAlso _threshold <= _graph.Count Then _
    Throw New TooComplexDifferenceException(String.Format("差分が複雑なため、エディットグラフの節点数が上限値({0})を超えました。", _threshold))
    End Sub

    ' ノードに子を追加
    Public Sub AddChild(parent As Tuple(Of Integer, Integer), child As Tuple(Of Integer, Integer))
    _parentMap.Add(child, parent)
    MakeNode(parent)
    Dim l = _graph(parent)
    l.Add(child)
    End Sub

    ' 指定の斜め線のY位置から一致終了の点までを探索
    Private Function Snake(k As Integer, y As Integer) As Integer
    Dim x = y - k
    While x < _a.Length And y < _b.Length AndAlso _a(x).Equals(_b(y))
    x += 1
    y += 1
    End While
    Return y
    End Function

    ' 添字の上下を指定できる配列
    Private Class MyArray
    Private _a() As Integer
    Private ReadOnly _lb As Integer
    Private ReadOnly _ub As Integer

    Public Sub New(lb As Integer, ub As Integer)
    ReDim _a(-lb + ub + 1)
    Initialize()
    _lb = lb
    _ub = ub
    End Sub

    Public Property Item(i As Integer) As Integer
    Get
    Return _a(i - _lb)
    End Get
    Set(value As Integer)
    _a(i - _lb) = value
    End Set
    End Property

    Public Sub Initialize()
    For i = 0 To _a.Length - 1
    _a(i) = -1
    Next
    End Sub
    End Class

    ' 差分が複雑すぎる場合に発生する例外
    Public Class TooComplexDifferenceException
    Inherits Exception
    Public Sub New(message As String)
    MyBase.New(message)
    End Sub
    End Class

    End Class


    美しいアルゴリズムは見るとゾクゾクしますね.
    スポンサーサイト

    テーマ : ソフトウェア開発
    ジャンル : コンピュータ

    tag : アルゴリズム O(NP) テキスト比較

    コメントの投稿

    非公開コメント

    プロフィール

    eikun

    Author:eikun
    なかなかやるきがでない人です

    えいくんち

    twitter

    pixiv

    最新記事
    最新コメント
    最新トラックバック
    月別アーカイブ
    カテゴリ
    検索フォーム
    RSSリンクの表示
    リンク
    ブロとも申請フォーム

    この人とブロともになる

    QRコード
    QR
    上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。