Совет конвертирования рекурсивного алгоритма Diff в итеративный?

Question

Приветствую!

Я написал алгоритм рекурсивного diff с нуля. Он находит «наилучшее соответствие» между двумя строками, так что различия сведены к минимуму и выдает две строки с любыми различиями, представленными в CAPS. Он отлично работает «как есть», за исключением того, что он довольно неэффективен. Я смотрел на него уже полтора дня, пытаясь найти способы сделать его итеративным или хотя бы уменьшить глубину стека, до которого он доходит, но я нахожусь в своем уме и надеялся, что здесь остроумный ум увидит решение более ясно, чем я.

Ниже приведено мясо кода. Класс MergePoint, на который делается ссылка, является просто узлом стиля «связанный список», который содержит «индекс в оригинале», целое число «индекс в измененном» и «следующий» MergePoint. Список MergePoint представляет собой серию индексов в каждом массиве, который был «объединен». Когда цепочка завершена, любые индексы, которые не представлены в цепочке, являются вставками/удалениями. Объект NullObject является расширением MergePoint, который, не забывая об этом, не обязательно нужно создавать и в принципе можно считать обычным «нулем».

Любые советы/предложения будут очень глубоко оценены.

public class StringCompare 
{ 
    public static int[][]  mergeList  = new int[0][0]; 
    public static MergePoint NULL   = NullObject.getNull(); 
    public static int   maxMerged  = 0; 
    public static int   minClusterSize = -1; 

    public static void diff(String orig, String alt) 
    { 
     String[] original = orig.toUpperCase().split(" "); 
     String[] altered = alt.toUpperCase().split(" "); 

     for(int i = 0; i < altered.length; i++) 
     { 
      merge(original, altered, 0, i, NULL, NULL, 0, 0); 
     } 


     for(int i = 0; i < mergeList.length; i++) 
     { 
      or[mergeList[i][0]] = or[mergeList[i][0]].toLowerCase(); 
      al[mergeList[i][1]] = al[mergeList[i][1]].toLowerCase(); 
     } 

     printStringArray(or); 
     printStringArray(al); 
    } 

    private void printStringArray(String[] arr) 
    { 
     for(String word : arr) 
     { 
      System.out.print(word.trim() + " "); 
     } 

     System.out.println(); 
    } 

    private static void merge(String[] original, String[] altered, int indexInOriginal, int indexInAltered, MergePoint head, MergePoint tail, int listSize, int clusters) 
    { 
     if (indexInOriginal >= original.length) 
     {   
      if (listSize > 0) 
      { 
       if (((listSize == maxMerged) && (clusters < minClusterSize)) || 
        (listSize > maxMerged)) 
       { 
        storeMergePoints(head, listSize, clusters); 
       } 
      } 
     } 
     else if (indexInAltered >= altered.length) 
     { 
      if (tail != NULL) 
      { 
       merge(original, altered, (indexInOriginal + 1), (tail.indexInNew() + 1), head, tail, listSize, clusters); 
      } 
      else 
      { 
       merge(original, altered, (indexInOriginal + 1), 0, head, tail, listSize, 0); 
      } 
     } 
     else 
     { 
      if(original[indexInOriginal].equals(altered[indexInAltered])) 
      { 
       MergePoint mergePoint = new MergePoint(indexInOriginal, indexInAltered); 
       MergePoint bookMark = NULL;    
       int   newClusters = clusters; 

       if (indexInOriginal != (tail.indexInOriginal() + 1)) 
       { 
        newClusters++; 
       } 

       if (indexInAltered != (tail.indexInNew() + 1)) 
       { 
        newClusters++; 
       } 

       if (head == NULL) 
       { 
        head = mergePoint; 
        tail = head; 
       } 
       else 
       { 
        tail.setNext(mergePoint); 

        bookMark = tail;     
        tail  = tail.next(); 
       } 

       merge(original, altered, (indexInOriginal + 1), (indexInAltered + 1), head, tail, (listSize + 1), newClusters); 

       if (bookMark == NULL) 
       { 
        merge(original, altered, indexInOriginal, (indexInAltered + 1), NULL, NULL, 0, 0); 
       } 
       else 
       { 
        bookMark.setNext(NULL); 

        merge(original, altered, indexInOriginal, (indexInAltered + 1), head, bookMark, listSize, newClusters); 
       } 
      } 
      else 
      { 
       merge(original, altered, indexInOriginal, (indexInAltered + 1), head, tail, listSize, clusters); 
      } 
     } 
    } 

    public static void storeMergePoints(MergePoint current, int size, int clusters) 
    {  
     mergeList  = new int[size][2]; 
     maxMerged  = size; 
     minClusterSize = clusters; 

     for(int i = 0; i < size; i++) 
     { 
      mergeList[i][0] = current.indexInOriginal(); 
      mergeList[i][1] = current.indexInNew(); 
      current   = current.next(); 
     }  
    } 
} 

Answer 1

Для замены рекурсии с итерацией вы можете рассмотреть вопрос о замене стеки виртуальной машины Java с помощью объекта стека, который вы контролируете: java.util.Stack будет вполне подходящим вариантом. Просто нажмите() и поп() свои данные в этом стеке на каждой итерации вместо того, чтобы вызвать вызов метода.