Comparator.java

Go to the documentation of this file.

/*
 * Project: Server for annotations sharing
 * Subproject: Position of fragment of text in XML document
 * Author: Michael Angelov
 * Edited by: Ing. Jaroslav Dytrych idytrych@fit.vutbr.cz, 
 *            Bc. Lukas Kubik xkubik22@stud.fit.vutbr.cz
 * File: Comparator.java
 * Description: Class consisting of traversing method and compare method
 */

/**
 * @file Comparator.java
 *
 * @brief Class consisting of traversing method and compare method
 */

/**
 * @package cz.vutbr.fit.knot.annotations.fragmentUpdater
 *
 * @brief Library for updating fragments of documents
 */
package cz.vutbr.fit.knot.annotations.fragmentUpdater;

import cz.vutbr.fit.knot.annotations.comet.Util;
import cz.vutbr.fit.knot.annotations.fragmentUpdater.compareMethods.CompareMethod;
import java.util.ArrayList;
import java.util.Iterator;
import javax.xml.xpath.XPathExpressionException;
import org.w3c.dom.Node;

/**
 * Comparator class consisting of traversing method and compare method
 *
 * @brief Class consisting of traversing method and compare method
 * @author Michael Angelov
 */
public class Comparator {

  /** 
   * Names of traversing methods 
   * 
   * @brief Names of traversing methods 
   */
  public enum TraversingMethod {
    STATIC, CHARACTER, CHARACTER_BIDIRECTIONALLY, WORD, FIRST_AND_LAST_WORD_THEN_LETTER
  };

  /** Traversing method */
  private TraversingMethod traversingMethod;
  /** Compare method */
  private CompareMethod compareMethod;
  /** Maximal enlargement of fragment length */
  private double maxLenghtEnlargement = 1.5;
  /** Maximal reduction of fragment length */
  private double maxLenghtReduction = 0.5;

  /**
   * Getter for traversing method used in comparator
   *
   * @return traversing method used in comparator
   */
  public TraversingMethod getTraversingMethod() {
    return traversingMethod;
  }

   /**
   * Getter for compare method used in comparator
   *
   * @return compare method used in comparator
   */
  public CompareMethod getCompareMethod() {
    return compareMethod;
  }
  
  /**
   * Setter for maximum annotation length enlargement used in
   * FIRST_AND_LAST_WORD method
   * 
   * @param maxLenghtEnlargement maximum annotation length enlargement 
   */
  public void setmaxLenghtEnlargement(double maxLenghtEnlargement){
    this.maxLenghtEnlargement = maxLenghtEnlargement;
  }

  /**
   * Constructor
   *
   * @param compareMethod compare method used to determine if strings match
   * @param traversingMethod traversing method in strings
   */
  public Comparator(CompareMethod compareMethod, TraversingMethod traversingMethod) {
    this.compareMethod = compareMethod;
    this.traversingMethod = traversingMethod;
  }
  
  /**
   * Constructor
   * 
   * @param compareMethod compare method used to determine if strings match
   * @param traversingMethod traversing method in strings
   * @param maxLenghtEnlargement maximum annotation length enlargement
   * @param maxLenghtReduction maximum annotation length reduction
   */
  public Comparator(CompareMethod compareMethod, TraversingMethod traversingMethod, 
          double maxLenghtEnlargement, double maxLenghtReduction) {
    this.compareMethod = compareMethod;
    this.traversingMethod = traversingMethod;
    this.maxLenghtEnlargement = maxLenghtEnlargement;
    this.maxLenghtReduction = maxLenghtReduction;
  }

  /**
   * Overriden toString() method
   *
   * @return string representation of comparator
   */
  @Override
  public String toString() {
    String tm = "";
    switch (traversingMethod) {
      case CHARACTER:
        tm = "Character";
        break;
      case CHARACTER_BIDIRECTIONALLY:
        tm = "Character_bidirectionally";
        break;
      case WORD:
        tm = "Word";
        break;
      case FIRST_AND_LAST_WORD_THEN_LETTER:
        tm = "First_and_last_word_then_letter";
        break;
      default:
        tm = "Static";
        break;
    }
    return compareMethod + " (" + tm + ")";
  }


  /**
   * Fragment compare method
   *
   * @param queryFragment fragment to be matched in node
   * @param node node in which string content of queryFrament should be matched
   * @return result fragment, null if there was no match
   */
  public UpdatableFragment compare(UpdatableFragment queryFragment, Node node) throws XPathExpressionException {

    int beginIndex, endIndex;
    String nodeSubstring = "", XPathString;

    if (getNodeContent(node) == null || (getNodeContent(node).length() < queryFragment.getLength())) {
      return null;
    }

    // determining which traversing method should be used
    switch (traversingMethod) {
      // offset and length of queryFragment are strictly used
      case STATIC:
        beginIndex = queryFragment.getOffset();
        endIndex = beginIndex + queryFragment.getLength();

        // if node text too short, skip
        if (endIndex > getNodeContent(node).length()) {
          return null;
        }

        nodeSubstring = getNodeContent(node).substring(beginIndex, endIndex);

        // if comparison is successful, return XPath position of node in which match occured
        if (compareMethod.compare(queryFragment.getText(), nodeSubstring) == true) {
          XPathString = XPathHelper.XPathStringOfNode(node);

          // return brand new result fragment
          return new UpdatableFragment(XPathString, queryFragment.getOffset(),
                                      queryFragment.getLength(), nodeSubstring);
        }

        break;
      
      // string traversing method with "character bidirectional step"
      case CHARACTER_BIDIRECTIONALLY:
        // indexes for bidirectional iteration
        int beginIndexL, beginIndexR, endIndexL, endIndexR;
        beginIndexL = beginIndexR = queryFragment.getOffset();
        endIndexL = endIndexR = beginIndexL + queryFragment.getLength();
        
        // check fragment position and shift it to the end of element if the offset is bad.
        if(endIndexL > getNodeContent(node).length()){
          endIndexL = endIndexR = getNodeContent(node).length();
          beginIndexL = beginIndexR = endIndexL - queryFragment.getLength();
        }

        // loop end condition (Stops the loop when both iteration ends.)
        boolean endIteration = false;
        // stepping through string
        while(!endIteration){
          endIteration = true;
          
          // Iterating to right from the original offset
          if(endIndexR <= getNodeContent(node).length()){
            nodeSubstring = getNodeContent(node).substring(beginIndexR, endIndexR);
            
            // if comparison is successful, return XPath position of node in which match occured
            if (compareMethod.compare(queryFragment.getText(), nodeSubstring) == true) {
              XPathString = XPathHelper.XPathStringOfNode(node);

              // return brand new result fragment
              return new UpdatableFragment(XPathString, beginIndexR,
                                        queryFragment.getLength(), nodeSubstring);
            }
            ++beginIndexR;
            ++endIndexR;
            endIteration = false;
          }
          
          // Iterating to left from the original offset
          if(beginIndexL >= 0){
            nodeSubstring = getNodeContent(node).substring(beginIndexL, endIndexL);
            
            // if comparison is successful, return XPath position of node in which match occured
            if (compareMethod.compare(queryFragment.getText(), nodeSubstring) == true) {
              XPathString = XPathHelper.XPathStringOfNode(node);

              // return brand new result fragment
              return new UpdatableFragment(XPathString, beginIndexL,
                                        queryFragment.getLength(), nodeSubstring);
            }
            --beginIndexL;
            --endIndexL;
            endIteration = false;
          }
        }
        break;

      // string traversing method with "character step"
      case CHARACTER:
        beginIndex = 0;
        endIndex = beginIndex + queryFragment.getLength();

        // stepping through string
        while (endIndex <= getNodeContent(node).length()) {
          nodeSubstring = getNodeContent(node).substring(beginIndex, endIndex);

          // if comparison is successful, return XPath position of node in which match occured
          if (compareMethod.compare(queryFragment.getText(), nodeSubstring) == true) {
            XPathString = XPathHelper.XPathStringOfNode(node);

            // return brand new result fragment
            return new UpdatableFragment(XPathString, beginIndex,
                                      queryFragment.getLength(), nodeSubstring);
          }

          beginIndex++;
          endIndex++;
        }

        break;

      // string traversing method with "word step" comparing first and last word of the fragment
      case FIRST_AND_LAST_WORD_THEN_LETTER:
        ArrayList<IndexAndlength> firstWordsHit = new ArrayList<IndexAndlength>();
        ArrayList<IndexAndlength> lastWordsHit = new ArrayList<IndexAndlength>();
        
        UpdatableFragment fr = firstAndLastWordMatchMethod(node, queryFragment, firstWordsHit, lastWordsHit);
        if(fr != null){
          return fr;
        }
        
        return firstAndLastLetterMatchMethod(node, queryFragment, firstWordsHit, lastWordsHit);
        
      // string traversing method with "word step"
      case WORD:
        return wordMatchMethod(node, queryFragment);
        
    }  // switch (traversingMethod)

    // there was no success in matching, return null
    return null;
  }  // compare()
    
  /**
   * Gets content of XML node
   *
   * @param node Node with content
   * @return If it's text node or CDATA, returns textual content of XML node, null otherwise
   */
  public static String getNodeContent(Node node) {
    if (node == null) {
      return null;
    }
    if (node.getNodeType() == Node.TEXT_NODE || node.getNodeType() == Node.CDATA_SECTION_NODE) {
      return node.getNodeValue();
    }

    return null;
  }  // getNodeContent()
  
  /**
   * Selects the best substrings of the new matched fragment.
   * Best == least different from the original fragment
   * 
   * @param origFragment Original fragment
   * @param newFragment Matched fragment
   * @return least different part of the matched fragment
   * @throws XPathExpressionException 
   */
  private UpdatableFragment selectBestPart(UpdatableFragment origFragment, UpdatableFragment newFragment) 
          throws XPathExpressionException {
      String words[] = newFragment.getText().split(" "); // new fragment words
      int minBadnessBeg, minBadnessEnd, badness; // tresholds
      minBadnessBeg = badness = Integer.MAX_VALUE;
      
      String origText = origFragment.getText();  // original annotated text
      int origOffset = origFragment.getOffset();  // original offset
      
      String origNewText = newFragment.getText(); // new fragment annotated text
      int origNewOffset = newFragment.getOffset(); // new fragment offset
      String origNewXpath = newFragment.getXPathString();
      
      int maxIterations = words.length;
      int index = 0;
      int index2 = 0;
      String newPart = ""; // currently matched substring
      String minPart = ""; // lest different substring in iteration
      int minOffset = 0;  // lest different substring offset in iteration
      
      // lest different subfragments in all iterations
      ArrayList<UpdatableFragment> BestSubParts = new ArrayList<UpdatableFragment>();
      
      // removing from the beginning of the fragment
      while(index < maxIterations){
          int newOffset = countWordsLengthBeg(index, words); // offset of the beginning od the next matched substring
          String removedFromBeg = origNewText.substring(newOffset); // currently matched substring cut from the beginning
          
          // result for the beginning cut
          int LD = Util.levenshtein(origText, removedFromBeg);
          double LPerc = (LD / (double)origText.length()) * 100;
          
          badness = 5* (int)LPerc + Math.abs(origOffset - newOffset);
          
          // if the previous result was better then end the iteration
          if(badness > minBadnessBeg){
            break;
          }
          else{ // else lower the treshold
            minBadnessBeg = badness;
          }
          
          // reset the treshold for the end cut
          minBadnessEnd = Integer.MAX_VALUE;
          
          // removing from the end of the fragment
          while(index2 < (maxIterations-index)){
            // currently matched substring cut from the end
            newPart = removedFromBeg.substring(0, countWordsLengthEnd(index2, words, removedFromBeg.length()));
            // result for the end cut
            int LD2 = Util.levenshtein(origText, newPart);
            double LPerc2 = (LD2 / (double)origText.length()) * 100;
            
            badness = 5 * (int)LPerc2 + Math.abs(origOffset - newOffset);
            
            // if the previous result was better then end the iteration
            if(badness > minBadnessEnd){
              break;
            }
            // else lower the treshold and remember the better substring
            else{
              minBadnessEnd = badness;
              minPart = newPart;
              minOffset = newOffset;
            }
            ++index2;
          }
          
          // add the best subfragment
          BestSubParts.add(new UpdatableFragment(origNewXpath, origNewOffset+minOffset, minPart.length(), minPart));

          // reset the inner index (end cut)
          index2 = 0;
          
          // raise the outer index (beggining cut)
          ++index;
      }
      
      // Select the least different subfragment
      if(BestSubParts.size() > 1){
        return selectBestSubFragment(origFragment, BestSubParts);
      }
      // If there was only one result then return it
      else if(BestSubParts.size() == 1){
        return BestSubParts.get(0);
      }
      
      // This should never happen
      return null;
  }
  
  /**
   * What is the offset of the n-th word from the beginning in the string with gaps?
   * 
   * @param count n
   * @param words All words
   * @return offset of the n-th word from the beginning od the string
   */
  private int countWordsLengthBeg(int count, String words[]){
      int offset = 0;
      for(int i = 0; i < count; i++){
          offset += words[i].length()+1;
      }
      return offset;
  }
  
  /**
   * What is the offset of the n-th word from the end in the string with gaps?
   * 
   * @param count n
   * @param words All words
   * @param wholeLength Length of the whole string with gaps
   * @return offset of the n-th word from the end od the string
   */
  private int countWordsLengthEnd(int count, String words[], int wholeLength){
    int offset = wholeLength;
    for(int i = words.length-1; i >= words.length - count; i--){
        offset -= words[i].length()+1;
    }
    return offset;
  }
  
  /**
   * Selects the best fragment from the best substrings
   * 
   * @param origFragment Original fragment
   * @param BestSubParts Best substrings
   * @return New selected fragment
   * @throws XPathExpressionException 
   */
  private UpdatableFragment selectBestSubFragment(UpdatableFragment origFragment,
          ArrayList<UpdatableFragment> BestSubParts)
          throws XPathExpressionException{
    if(BestSubParts.isEmpty()){
      return null;
    }
    else if(BestSubParts.size() == 1){
      return BestSubParts.get(0);
    }
    
    int minBadness = Integer.MAX_VALUE; //treshold
    
    String originalText = origFragment.getText(); // original fragment text
    int orignalOffset = origFragment.getOffset(); // original fragment offset
    
    Iterator<UpdatableFragment> itFrg = BestSubParts.iterator(); // best subfragments iterator
    
    UpdatableFragment comparedfragment; // currently compared fragment
    
    int index = 0; // current index
    int bestIndex = 0; // index of the best fragment text
    
    // finds the best substring
    while(itFrg.hasNext()){
      comparedfragment = itFrg.next();
      
      int LD = Util.levenshtein(originalText, comparedfragment.getText());
      double LPerc = (LD / (double)originalText.length()) * 100;
      
      int badness = 5 * (int)LPerc + 
              Math.abs(orignalOffset - comparedfragment.getOffset());
      if(badness < minBadness){
        minBadness = badness;
        bestIndex = index;
      }
      ++index;
    }
    
    return BestSubParts.get(bestIndex);
  }
  
  /**
   * Method which is matching over all words of the fragment
   * 
   * @param node node in which string content of queryFrament should be matched
   * @param queryFragment fragment to be matched in node
   * @return result fragment, null if there was no match
   * @throws XPathExpressionException 
   */
  private UpdatableFragment wordMatchMethod(Node node, UpdatableFragment queryFragment) 
          throws XPathExpressionException
  {
    String[] words = getNodeContent(node).split(" ");
    int wordOffset = 0;
    StringBuilder nodeSb;
    // was any match in this substring?
    boolean match = false;
    StringBuilder newFragment = new StringBuilder();
    int newFragmentOffset = 0;

    // all the best matched subfragments
    ArrayList<UpdatableFragment> bestFragments = new ArrayList<UpdatableFragment>();

    // iterating through all of the words in node
    for (int i = 0; i <= words.length - queryFragment.getWordCount(); i++) {
      nodeSb = new StringBuilder();
      if(i > 0){
        wordOffset += words[i-1].length()+1;
      }

      // comparing the same number of words in node that is in queryFragment
      for (int j = 0; j < queryFragment.getWordCount(); j++) {
        nodeSb.append(words[i + j]);
        if (j != queryFragment.getWordCount() - 1) {
          nodeSb.append(' ');
        }
      }

      // if comparison is successful, add the substring to the compared string
      if (compareMethod.compare(queryFragment.getText(), nodeSb.toString()) == true) {          
        if(match == false){ // new match
            newFragment = new StringBuilder(nodeSb.toString());
            newFragmentOffset = wordOffset;
            match = true;
        }
        else{ // at least one match was before this match
            newFragment.append(' ');
            newFragment.append(words[i + queryFragment.getWordCount()-1]);
        }
      }
      // no match and substring is filled then select the best part of it
      else if(match == true){
          match = false;

          UpdatableFragment fr = new UpdatableFragment(XPathHelper.XPathStringOfNode(node), newFragmentOffset,
                newFragment.length(), newFragment.toString());

          bestFragments.add(selectBestPart(queryFragment, fr));
      }
    }

    // Select the least different matched subfragment
    if(bestFragments.size() > 1){
      return selectBestSubFragment(queryFragment, bestFragments);
    }
    // If there was only one result then return it
    else if(bestFragments.size() == 1){
      return bestFragments.get(0);
    }
    else{
      return null;
    }
  }
    
  /**
   * Method which is matching first and last word of the original fragment
   * 
   * @param node node in which string content of queryFrament should be matched
   * @param queryFragment fragment to be matched in node
   * @param firstWordsHit Initialized arraylist for storing first word of the fragment
   *                      match hit in the node.
   * @param lastWordsHit Initialized arraylist for storing last word of the fragment
   *                     match hit in the node.
   * @return result fragment, null if there was no match
   * @throws XPathExpressionException 
   */
  private UpdatableFragment firstAndLastWordMatchMethod(Node node, UpdatableFragment queryFragment,
          ArrayList<IndexAndlength> firstWordsHit, ArrayList<IndexAndlength> lastWordsHit) 
          throws XPathExpressionException
  {
    if(queryFragment.getWordCount() <= 1){
      return null;
    }
    
    // Content of the node
    String[] words = getNodeContent(node).split(" ");
    // Fragment words
    String[] fragmentWords = queryFragment.getText().split(" ");
    // Original fragment XPath
    String XPath = XPathHelper.XPathStringOfNode(node);
    
    // First word of the original fragment
    String firstWord = fragmentWords[0];
    // Last word of the original fragment
    String lastWord = fragmentWords[fragmentWords.length-1];
    
    // Variable with the starting index and the starting offset
    IndexAndlength IaL = new IndexAndlength();
    // Maximum length of the new fragment
    int maxLength = (int) (queryFragment.getLength() * this.maxLenghtEnlargement);
    // Minimum length of the new fragment
    int minLength = (int) (queryFragment.getLength() * this.maxLenghtReduction);
    
    // all the best matched subfragments
    ArrayList<UpdatableFragment> bestFragments = new ArrayList<UpdatableFragment>();

    // iterating through all of the words in node
    while(IaL.index < words.length){
      IaL.index = matchFirstWord(words, firstWord, lastWord, IaL, firstWordsHit, lastWordsHit);
      // if the first word is same as the original first word
      if(IaL.index != null){
        ++IaL.index;
        UpdatableFragment fr = matchLastWord(words, lastWord, IaL, 
                maxLength, minLength, XPath);
        // if the last word is same as the original last word then we add the fragment to the best fragments
        if(fr != null){
          bestFragments.add(fr);
        }
        IaL.offset += words[IaL.index-1].length()+1;
      }
      else{
        break;
      }
    }
    
    // Selects the best fragment from subfragments
    return selectBestSubFragment(queryFragment, bestFragments);
  }
  
  /**
   * Finds the first occurrence of the word in the String array nodeWords
   * 
   * @param nodeWords Words of the node
   * @param firstWord First word which we are looking for
   * @param lastWord Last word which we are looking for
   * @param IaL Variable with the starting index and the starting offset
   * @param firstWordsHit Array to which found positions of first word will be stored
   * @param lastWordsHit Array to which found positions of last word will be stored
   * @return new offset
   */
  private Integer matchFirstWord(String[] nodeWords, String firstWord, String lastWord, 
          IndexAndlength IaL, ArrayList<IndexAndlength> firstWordsHit, ArrayList<IndexAndlength> lastWordsHit)
  {
    for (int i = IaL.index; i <= nodeWords.length-1; i++) {
      if(i > 0){
        IaL.offset += nodeWords[i-1].length()+1;
      }
      if (compareMethod.compare(firstWord, nodeWords[i]) == true) {
        IaL.comparedWordLength = nodeWords[i].length();
        IndexAndlength IaLHit = new IndexAndlength(i, IaL.comparedWordLength, IaL.offset);
        firstWordsHit.add(IaLHit);
        return i;
      }
      else if(compareMethod.compare(lastWord, nodeWords[i]) == true){
        IndexAndlength IaLHit = new IndexAndlength(i, nodeWords[i].length(), IaL.offset);
        lastWordsHit.add(IaLHit);
      }
    }
    
    return null;
  }
  
  /**
   * Finds the last occurrence of the word in the String array nodeWords
   * 
   * @param nodeWords Words of the node
   * @param word Word which we are looking for
   * @param IaL Variable with the starting index and the starting offset
   * @param maxLength Maximum length of the new fragment
   * @param minLength Minimal length of the new fragment
   * @param XPath New fragment XPath
   * @return New fragment or null if no fragment was found.
   * @throws XPathExpressionException 
   */
  private UpdatableFragment matchLastWord(String[] nodeWords, String word, 
          IndexAndlength IaL, int maxLength, int minLength, String XPath) throws XPathExpressionException 
  {
    // maximum length of the fragment - first word
    int maxSize = maxLength - (IaL.comparedWordLength);
    int actualSize = 0;

    for (int i = IaL.index; i <= nodeWords.length-1; i++) {
      actualSize += nodeWords[i].length()+1;
      if(actualSize > maxSize){
        return null;
      }
      if (compareMethod.compare(word, nodeWords[i]) == true) { 
        String fragmentString = createFragmentStringFromWords(nodeWords, IaL.index-1, i);
        if(fragmentString.length() < minLength){
          return null;
        }
        else{
          return new UpdatableFragment(XPath, IaL.offset, fragmentString.length(), fragmentString);
        }
      }
    }
    
    return null;
  }
  
  /**
   * Creates a new fragment string from the words in array words.
   * Inserts spaces between the words.
   * 
   * @param words Words array used for the creation of the fragment string
   * @param firstWordIndex Index of the first word.
   * @param lastWordIndex Index of the last word.
   * @return String with the new fragment.
   */
  private String createFragmentStringFromWords(String[] words, int firstWordIndex, int lastWordIndex){
    StringBuilder sb = new StringBuilder();
    for(int i = firstWordIndex; i <= lastWordIndex; i++){
      sb.append(words[i]);
      if(i < lastWordIndex){
        sb.append(' ');
      }
    }
    return sb.toString();
  }
  
  /**
   * Method which is matching first or last word and last or first letter of the original fragment
   * It's based in similiar idea as firstAndLastWordMatchMethod
   * 
   * @param node node in which string content of queryFrament should be matched
   * @param queryFragment fragment to be matched in node
   * @param firstWordsHit Initialized arraylist with stored first words of the fragment
   *                      match hit in the node.
   * @param lastWordsHit Initialized arraylist with stored last words of the fragment
   *                     match hit in the node.
   * @return result fragment, null if there was no match
   * @throws XPathExpressionException 
   */
  private UpdatableFragment firstAndLastLetterMatchMethod(Node node, UpdatableFragment queryFragment,
          ArrayList<IndexAndlength> firstWordsHit, ArrayList<IndexAndlength> lastWordsHit) 
          throws XPathExpressionException
  {
    if(firstWordsHit.isEmpty() && lastWordsHit.isEmpty()){
      return null;
    }
    
    String[] words = getNodeContent(node).split(" ");
    String[] fragmentWords = queryFragment.getText().split(" ");
    String XPath = XPathHelper.XPathStringOfNode(node);
    
    String firstWord = fragmentWords[0];
    String lastWord = fragmentWords[fragmentWords.length-1];
    
    ArrayList<UpdatableFragment> matchedFragments = new ArrayList<UpdatableFragment>();
    
    int maxLength = (int) (queryFragment.getLength() * this.maxLenghtEnlargement);
    int minLength = (int) (queryFragment.getLength() * this.maxLenghtReduction);
    
    Iterator<IndexAndlength> it = firstWordsHit.iterator();
    
    IndexAndlength IaL;
    while(it.hasNext()){
      IaL = it.next();
      UpdatableFragment fr;
      fr = matchSameLastLetter(words, lastWord, IaL, maxLength, minLength, XPath);
      if(fr != null){
        matchedFragments.add(fr);
      }
    }
    
    it = lastWordsHit.iterator();
    
    while(it.hasNext()){
      IaL = it.next();
      UpdatableFragment fr = matchSameFirstLetter(words, firstWord, IaL, maxLength, minLength, XPath);
      if(fr != null){
        matchedFragments.add(fr);
      }
    }
    
    // If we haven't matched any fragment then we try to find the most similiar fragment
    if(matchedFragments.isEmpty()){
      it = firstWordsHit.iterator();
      
      while(it.hasNext()){
        IaL = it.next();
        UpdatableFragment fr;
        fr = matchMostSimiliar(words, IaL, maxLength, minLength, XPath, queryFragment.getText());
        if(fr != null){
          matchedFragments.add(fr);
        }
      }
    }
    
    return selectBestSubFragment(queryFragment, matchedFragments);
  }
  
  /**
   * Method searches for the first word with the same last letter as the word in parameter word.
   * 
   * @param nodeWords Words of the node
   * @param word Word which we are looking for
   * @param IaL Variable with the starting index and the starting offset
   * @param maxLength Maximum length of the new fragment
   * @param minLength Minimal length of the new fragment
   * @param XPath New fragment XPath
   * @return New fragment or null if no fragment was found.
   * @throws XPathExpressionException 
   */
  private UpdatableFragment matchSameLastLetter(String[] nodeWords, String word, 
          IndexAndlength IaL, int maxLength, int minLength, String XPath)
          throws XPathExpressionException 
  {
    
    int maxSize = maxLength - (IaL.comparedWordLength);
    int actualSize = 0;
    
    char lastLetter = word.charAt(word.length()-1);
    
    for(int i = IaL.index+1; i < nodeWords.length; i++){
      actualSize += nodeWords[i].length()+1;
      if(actualSize > maxSize){
        return null;
      }
      if(nodeWords[i].charAt(nodeWords[i].length()-1) == lastLetter) { 
        String fragmentString = createFragmentStringFromWords(nodeWords, IaL.index, i);
        if(fragmentString.length() < minLength){
          return null;
        }
        else{
          return new UpdatableFragment(XPath, IaL.offset, fragmentString.length(), fragmentString);
        }
      }
    }
    return null;
  }
  
  /**
   * Method searches backwards for the first word with the same first letter 
   * as the word in parameter word.
   * 
   * @param nodeWords Words of the node
   * @param word Word which we are looking for
   * @param IaL Variable with the starting index and the starting offset
   * @param maxLength Maximum length of the new fragment
   * @param minLength Minimal length of the new fragment
   * @param XPath New fragment XPath
   * @return New fragment or null if no fragment was found.
   * @throws XPathExpressionException 
   */
  private UpdatableFragment matchSameFirstLetter(String[] nodeWords, String word, 
          IndexAndlength IaL, int maxLength, int minLength, String XPath)
          throws XPathExpressionException 
  {
    
    int maxSize = maxLength - (IaL.comparedWordLength);
    int actualSize = 0;
    
    char firstLetter = word.charAt(0);
    
    for(int i = IaL.index-1; i >= 0; i--){
      actualSize += nodeWords[i].length()+1;
      if(actualSize > maxSize){
        return null;
      }
      IaL.offset -= nodeWords[i].length()+1;
      if(nodeWords[i].charAt(0) == firstLetter) { 
        String fragmentString = createFragmentStringFromWords(nodeWords, i, IaL.index);
        if(fragmentString.length() < minLength){
          return null;
        }
        else{
          return new UpdatableFragment(XPath, IaL.offset, fragmentString.length(), fragmentString);
        }
      }
    }
    return null;
  }
  
   /**
   * Method creates a fragment with most compatible words and the least 
   * levenstein distance from original fragment.
   * 
   * @param nodeWords Words of the node
   * @param IaL Variable with the starting index and the starting offset
   * @param maxLength Maximum length of the new fragment
   * @param minLength Minimum length of the new fragment
   * @param XPath New fragment XPath
   * @param originalFragment Text of the original fragment
   * @return New fragment or null if no fragment was found.
   * @throws XPathExpressionException 
   */
  private UpdatableFragment matchMostSimiliar(String[] nodeWords, 
          IndexAndlength IaL, int maxLength, int minLength, String XPath, String originalFragment)
          throws XPathExpressionException 
  {
    int distance = Integer.MAX_VALUE;
    
    int maxSize = maxLength - (IaL.comparedWordLength);
    int actualSize = 0;
    String bestFragment = null;
    
    for(int i = IaL.index+1; i < nodeWords.length; i++){
      actualSize += nodeWords[i].length()+1;
      if(actualSize > maxSize){
        return null;
      }
      String fragmentString = createFragmentStringFromWords(nodeWords, IaL.index, i);
      int newDistance;
      if((newDistance = Util.levenshtein(fragmentString, originalFragment)) <= distance){
        distance = newDistance;
        bestFragment = fragmentString;
      }
      // It will never be null because of the initial value of the distance.
      else if(bestFragment.length() >= minLength){
        return new UpdatableFragment(XPath, IaL.offset, bestFragment.length(), bestFragment);
      }
    }
    if(bestFragment == null || bestFragment.length() < minLength){
      return null;
    }
    else{
      return new UpdatableFragment(XPath, IaL.offset, bestFragment.length(), bestFragment);
    }
    
  }  // matchMostSimiliar()
  
  /**
   * Auxiliary class with index, offset and word length.
   * 
   * @brief Auxiliary class with index, offset and word length.
   */
  private class IndexAndlength {
    /** Index */
    public Integer index = 0;
    /** Compared word length */
    public int comparedWordLength = 0;
    /** Offset */
    public int offset = 0;
    
    /**
     * Default Constructor
     */
    public IndexAndlength(){
    
    }
    
    /**
     * Constructor
     * 
     * @param index Index
     * @param comparedWordLength Compared word length
     * @param offset Offset
     */
    public IndexAndlength(Integer index, int comparedWordLength, int offset){
      this.index = index;
      this.comparedWordLength = comparedWordLength;
      this.offset = offset;
    }
  }  // private class IndexAndlength
}  // class Comparator