Как вычислить расстояние редактирования дерева?

Ответ 1

Здесь java исходный код (gzipped tarball внизу) для алгоритма дерева Edit Edit, который может быть вам полезен.

На странице представлены ссылки и несколько слайдов, которые проходят шаг за шагом по алгоритму "Чжан и Шаша" и другие полезные ссылки, чтобы вы могли ускориться.

Изменить:. Хотя этот ответ был принят, поскольку он указывал на алгоритм Чжан-Шаши, код в ссылке имеет ошибки. Стив Джонсон и tim.tadh предоставили рабочий код Python. Подробнее см. комментарий Стив Джонсона.

Ответ 2

(Отредактирован этот ответ для ссылки на текущую версию реализации, заданную tim.tadh)

Эта библиотека Python правильно реализует алгоритм Чжан-Шаши: https://github.com/timtadh/zhang-shasha

Он начался как прямой порт источника Java, указанный в текущем принятом ответе (тот, который связан с ссылкой в ​​tarball), но эта реализация не соответствует правилу и почти невозможна для запуска вообще.

Ответ 3

Я написал реализацию (https://github.com/hoonto/jqgram.git) на основе существующего кода PyGram Python (https://github.com/Sycondaman/PyGram) для тех из вас, кто хочет использовать приближение расстояния до дерева, используя алгоритм PQ-Gram в браузере и/или в Node.js.

Модуль аппроксимации расстояния дерева дерева jqgram реализует алгоритм PQ-Gram для приложений на стороне сервера и на стороне браузера; O (n log n) и O (n), где n - количество узлов. См. Академическую статью, из которой следует алгоритм: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

Приближение PQ-Грама намного быстрее, чем получение истинного расстояния редактирования через Чжан и Шашу, Клейна или Гуа и др. al, которые предоставляют истинные алгоритмы дистанции редактирования, которые выполняют минимальное время O (n ^ 2) и поэтому часто непригодны.

Часто в реальных приложениях нет необходимости знать истинное расстояние редактирования, если можно получить относительное приближение нескольких деревьев к известному стандарту. Javascript, в браузере и теперь на сервере с появлением Node.js часто с древовидными структурами, и производительность конечного пользователя, как правило, важна для реализации и проектирования алгоритмов; таким образом, jqgram.

Пример:

var jq = require("jqgram").jqgram;
var root1 = {
    "thelabel": "a",
    "thekids": [
        { "thelabel": "b",
        "thekids": [
            { "thelabel": "c" },
            { "thelabel": "d" }
        ]},
        { "thelabel": "e" },
        { "thelabel": "f" }
    ]
}

var root2 = {
    "name": "a",
    "kiddos": [
        { "name": "b",
        "kiddos": [
            { "name": "c" },
            { "name": "d" },
            { "name": "y" }
        ]},
        { "name": "e" },
        { "name": "x" }
    ]
}

jq.distance({
    root: root1,
    lfn: function(node){ return node.thelabel; },
    cfn: function(node){ return node.thekids; }
},{
    root: root2,
    lfn: function(node){ return node.name; },
    cfn: function(node){ return node.kiddos; }
},{ p:2, q:3, depth:10 },
function(result) {
    console.log(result.distance);
});

Обратите внимание, что параметры lfn и cfn определяют, как каждое дерево должно определять имена ярлыков node и дочерний массив для каждого корня дерева независимо друг от друга, чтобы вы могли делать смешные вещи, например, сравнивая объект с DOM браузера. Все, что вам нужно сделать, это предоставить эти функции вместе с каждым корнем, а jqgram сделает все остальное, вызвав ваши lfn и cfn предоставленные функции для создания деревьев. Так что в этом смысле это (по-моему, так или иначе) гораздо проще в использовании, чем PyGram. Кроме того, его Javascript, так что используйте его клиент или сервер!

Теперь один из подходов, который вы можете использовать, - использовать jqgram или PyGram для получения нескольких близких деревьев, а затем использовать истинный алгоритм расстояния редактирования от меньшего набора деревьев, зачем тратить все вычисления на деревья, которые вы можете уже легко определить очень отдаленные, или наоборот. Таким образом, вы можете использовать jqgram, чтобы сузить выбор.

Надеюсь, что код поможет некоторым людям.

Ответ 4

Здесь вы найдете Java-реализации алгоритмов дистанции редактирования дерева:

http://www.inf.unibz.it/dis/projects/tree-edit-distance

В дополнение к алгоритму Zhang & Shasha от 1989 года существуют также варианты редактирования дерева редактирования более поздних алгоритмов, включая Klein 1998, Demaine et al. 2009, и алгоритм Robust Tree Edit Distance (RTED) от Pawlik & Augsten, 2011.

Ответ 5

Я создал простую оболочку python (apted.py) для алгоритма APTED, используя jpype, если кому-то интересно:

# To use, create a folder named lib next to apted.py, then put APTED.jar into it

import os, os.path, jpype 

global distancePackage
distancePackage = None

global utilPackage
utilPackage = None

def StartJVM():
  # from http://www.gossamer-threads.com/lists/python/python/379020
  root = os.path.abspath(os.path.dirname(__file__)) 
  jpype.startJVM(jpype.getDefaultJVMPath(), 
  "-Djava.ext.dirs=%s%slib" % (root, os.sep))
  global distancePackage
  distancePackage = jpype.JPackage("distance")
  global utilPackage
  utilPackage = jpype.JPackage("util")


def StopJVM():
  jpype.shutdownJVM()


class APTED:
  def __init__(self, delCost, insCost, matchCost):
    global distancePackage
    if distancePackage is None:
      raise Exception("Need to call apted.StartJVM() first")
    self.myApted = distancePackage.APTED(float(delCost), float(insCost), float(matchCost))

  def nonNormalizedTreeDist(self, lblTreeA, lblTreeB):
    return self.myApted.nonNormalizedTreeDist(lblTreeA.myLblTree, lblTreeB.myLblTree)


class LblTree:
  def __init__(self, treeString):
    global utilPackage
    if utilPackage is None:
      raise Exception("Need to call apted.StartJVM() first")

    self.myLblTree = utilPackage.LblTree.fromString(treeString)

'''
# Example usage:

import apted
apted.StartJVM()
aptedDist = apted.APTED(delCost=1, insCost=1, matchCost=1)
treeA = apted.LblTree('{a}')
treeB = apted.LblTree('{b{c}}')
dist = aptedDist.nonNormalizedTreeDist(treeA, treeB)
print dist


# When you are done using apted
apted.StopJVM()
# For some reason it doesn't usually let me start it again and crashes python upon exit when I do this so call only as needed
'''

Ответ 6

Существует версия журнала ICALP2007, на которую вы ссылаетесь на http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf Эта версия также имеет псевдокод.

Ответ 7

Существует много вариантов редактирования дерева. Если вы можете пойти с минимальным расстоянием редактирования дерева вниз, которое ограничивает вставки и удаляет листья, я предлагаю попробовать следующую статью: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965. Реализация представляет собой простую матрицу динамического программирования с стоимостью O (n2).

Ответ 8

Есть хорошая версия APTED на Python (расстояние редактирования дерева всех путей), доступная сейчас: https://pypi.org/project/apted/

Бумага (2016): расстояние редактирования дерева: надежный и эффективный для памяти, Pawlik и Augsten

Ответ 9

Я думаю, вы просто ищете кратчайший путь между двумя вершинами. Если это так, вы можете использовать Dijkstra algorithm. (На странице wikipedia есть псевдокод, на который вы можете ссылаться.)