Как я вычисляю древовидное расстояние редактирования?
Вот как я это сделал на существующей таблице и столбце (с именем id):
UPDATE table SET id=ROWNUM;
DECLARE
maxval NUMBER;
BEGIN
SELECT MAX(id) INTO maxval FROM table;
EXECUTE IMMEDIATE 'DROP SEQUENCE table_seq';
EXECUTE IMMEDIATE 'CREATE SEQUENCE table_seq START WITH '|| TO_CHAR(TO_NUMBER(maxval)+1) ||' INCREMENT BY 1 NOMAXVALUE';
END;
CREATE TRIGGER table_trigger
BEFORE INSERT ON table
FOR EACH ROW
BEGIN
:new.id := table_seq.NEXTVAL;
END;
4 ответа
Вот исходный код java (сжатый сжатый архив внизу) для алгоритма Tree Edit Distance, который может быть вам полезен.
Страница включает ссылки и несколько слайдов, которые шаг за шагом проходят через алгоритм «Чжан и Шаша», а также другие полезные ссылки, которые помогут вам быстрее освоиться.
Изменить: Хотя этот ответ был принят, поскольку он указывал на Чжан -Алгоритм Шаша, в коде по ссылке есть ошибки. Стив Джонсон и tim.tadh предоставили рабочий код Python . Подробнее см. комментарий Стива Джонсона .
Я думаю, вы просто ищете кратчайший путь между двумя вершинами. Если это так, вы можете использовать алгоритм Дейкстры . (На странице википедии есть псевдокод, к которому вы можете обратиться.)
Существует журнальная версия статьи ICALP2007, на которую вы ссылаетесь по адресу http: //www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf Эта версия также имеет псевдокод.
Существует много вариантов расстояния редактирования дерева. Если вы можете использовать расстояние редактирования дерева сверху вниз, которое ограничивает вставку и удаление листьев, я предлагаю попробовать следующий документ: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll = GUIDE & CFID = 68408627 & CFTOKEN = 54202965 . Реализация представляет собой простую матрицу динамического программирования со стоимостью O (n2).