词典、倒排记录表和容错式检索的实验_倒排索引跳表步长

（1）考虑利用如下带有跳表指针的倒排记录表

与两个中间结果表（如下所示，不存在跳表指针）分别进行合并操作。

3 5 96 99 100 101

25 60 68 120 150

采用教材《Introduction to Information Retrieval》第37页Figure 2.10中所描述的基于跳表指针（skip pointers）的倒排记录表（postings lists）合并算法，请问：

a.跳表指针实际跳转的次数分别是多少（也就是说，指针p1的下一步将跳到skip（p1））？请逐个列出来。

1、与3 5 96 99 100 101进行合并操作：

2次。24->75;75->92

2、与25 60 68 120 150进行合并操作：

3次。3->24;24->75;92->115

b.当两个表进行合并时，倒排记录之间的比较次数分别是多少？请逐个列出来。

1、与3 5 96 99 100 101进行合并操作：13次

2、与25 60 68 120 150进行合并操作：10次

c.如果不使用跳表指针，那么倒排记录之间的比较次数分别是多少？请逐个列出来。

1、与3 5 96 99 100 101进行合并操作：18次

2、与25 60 68 120 150进行合并操作：18次

（2）下面给出的是一个位置索引的一部分，格式为：doc1: <position1, position2, …>; doc2: <position1, position2, …>; …

angels: 2: <36,174,252,651>; 4: <12,22,102,432>; 7: <17>;

fools: 2: <1,17,74,222>; 4: <8,78,108,458>; 7: <3,13,23,193>;

fear: 2: <37,87,704,722,901>; 4: <13,43,113,433>; 7: <18,328,528>;

in: 2: <3,37,76,444,851>; 4: <12,20,110,470,500>; 7: <5,15,25,195>;

rush: 2: <3,66,194,321,702>; 4: <9,69,149,429,569>; 7: <4,14,404>;

to: 2: <47,86,234,999>; 4: <14,24,774,944>; 7: <199,319,599,709>;

tread: 2: <57,94,333>; 4: <15,35,155>; 7: <20,320>;

where: 2: <67,124,393,1001>; 4: <11,41,101,421,431>; 7: <16,36,736>; 

请问哪些文档和以下的查询匹配（请给出解答过程）？其中引号内的每个表达式都是一个短语查询。

---

a.“angels fear”

已知：

angels: 2: <36,174,252,651>; 4: <12,22,102,432>; 7: <17>;

fear: 2: <37,87,704,722,901>; 4: <13,43,113,433>; 7: <18,328,528>;

思路：

①首先检查文档编号：

②开始检查表中位置是否有一个fear前面的单词是angels；

• docID(angels) = 2与docID(fear) = 2，开始检查表中位置是否有一个fear前面的单词是angels；

经检查angels:2：<36>;

           Fear：2：<37>;

• docID(angels) = 4与docID(fear) = 4，开始检查表中位置是否有一个fear前面的单词是angels；

经检查：angels:2：<36>;4<12,432>

               Fear：2：<37>;4<13,433>

• docID(angels) = 7与docID(fear) = 7，开始检查表中位置是否有一个fear前面的单词是angels；

经检查：angels:2：<36>;4<12,432>;7<17>

               Fear：2：<37>;4<13,433>;7<18>

综上所述：angels:2：<36>;4<12,432>;7<17>

                  Fear：2：<37>;4<13,433>;7<18>

文档2、4、7；

b.“angels fear to tread”

已知： 

angels: 2: <36,174,252,651>; 4: <12,22,102,432>; 7: <17>;

fear: 2: <37,87,704,722,901>; 4: <13,43,113,433>; 7: <18,328,528>;

to: 2: <47,86,234,999>; 4: <14,24,774,944>; 7: <199,319,599,709>;

tread: 2: <57,94,333>; 4: <15,35,155>; 7: <20,320>;

思路：

①将“angels fear to thread”拆分成“angels fear”、“fear to”、“ to thread”，分别搜索这三个词条的文档位置；

②对搜索结果进行检查；

解决：

·根据题2搜索结果，已知angels和fear的搜索结果为：

angels:2：<36>;4<12,432>;7<17>

fear：2：<37>;4<13,433>;7<18>

在文档2、4、7；

• ·对于fear和to进行搜索：

fear：2：<37>;4<13,433>;7<18>

to:   2: <47,86,234,999>; 4: <14,24,774,944>; 7: <199,319,599,709>;

 - 先检查文档号

   docID(fear) = 4与docID(to) = 4,检查对应的位置索引；发现没有符合条件的词条，跳过；

   docID(fear) = 4与docID(to) = 4,检查对应的位置索引；经过检查，发现：

     fear : 4<13>;

     to  : 4<14>;

   docID(fear) = 4与docID(to) = 4,检查对应的位置索引；发现没有符合条件的词条，跳过；

     fear : 4<13>;

     to  : 4<14>;

只有文档4；

• ·对to和thread进行搜索：

to     : 4<14>;

Thread :2: <57,94,333>; 4: <15,35,155>; 7: <20,320>;

仍然采用上述步骤进行说明：

DocId(to) = 4 和docId(thread) = 4，检查对应的位置索引；经过检查，发现：

to    : 4<14>;

thread : 4<15>;

只有文档4；

·对angels的文档进行删除，只留：

angels：4<12>;

·对结果进行检查：

angels:2：4<12>;

fear  : 4<13>;

to   : 4<14>;

thread : 4<15>;

对四个词在文档中的位置进行检索：发现符合条件，得到结果：

文档4

c.“angels fear to tread”AND“fools rush in”

因为“angels fear to thread”只存在于文档4，所以只在文档4中对“fools rush in”进行查找；

①按照上题的方式，仍然进行词项拆分

·“fools rush”

fools: 2: <1,17,74,222>; 4: <8,78,108,458>; 7: <3,13,23,193>;

rush: 2: <3,66,194,321,702>; 4: <9,69,149,429,569>; 7: <4,14,404>;

   - docID(fools) = 2与docID(rush) = 2进行检查，发现没有符合题意的索引，跳过；

   - docID(fools) = 4与docID(rush) = 4进行检查，发现：

fools: 4: <8>;

rush: 4: <9>;

   - docID(fools) = 7与docID(rush) = 7进行检查，发现：

fools:4: <8>; 7: <3,13>;

rush: 4: <9>; 7: <4,14>;

·“rush in”

rush: 4: <9>; 7: <4,14>;

in: 2: <3,37,76,444,851>; 4: <12,20,110,470,500>; 7: <5,15,25,195>;

- docID(rush) = 2与docID(in) = 2进行检查;发现没有符合题意的索引，跳过；

- docID(rush) = 4与docID(in) = 4进行检查;发现没有符合题意的索引，跳过；

- docID(rush) = 7与docID(in) = 7进行检查;发现：

rush:7: <4,14>;

in:  7: <5,15>;

②将词项综合一起分析：

发现：

fools:7: <3,13>;

rush: 7: <4,14>;

in :  7: <5,15>;

综上所述：“fools rush in”在文档7；“angels fear to thread”在文档4；

两者And后结果为空集。

---

（3）阅读教材《Introduction to Information Retrieval》第37页Figure 2.10中所描述的基于跳表指针（skip pointers）的倒排记录表（postings lists）合并算法，并用Java语言或其他常用语言实现该算法。要求在题(1)的例子上验证算法的正确性。

根据算法提示，构想出建立三个类：分别为docID类、SkipAnd类，和对应的Test类；

1. ①docID类包含两个参数：docID，以及其对应的跳转指针的信息；

class docID{
    private int docID;//顾名思义，就是docID
    private int hasSkip;//是否含有跳转指针，如果有，置skip步数；如果没有，置0；
    public docID(int docID,int hasSkip){
        this.docID = docID;
        this.hasSkip = hasSkip;
    }
    //获取跳转指针信息
    public int getHasSkip(){
        return this.hasSkip;
    }
    //获取对应的docID
    public int getDocID(){
        return this.docID;
    }
}

1. ②SkipAnd类包含两个参数，分别为将要进行与操作的倒排索引表；

2. class SkipAnd {
       private ArrayList<docID> Inversion_Form1;//倒排索引表1
       private ArrayList<docID> Inversion_Form2;//倒排索引表2
   

   建立构造函数，对倒排索引表1和2进行初始化操作；

3.     public SkipAnd(int[] arr1, int[] arr2,int skip1,int skip2){
           //初始化两个含有跳表指针的倒排记录表
           docID t;
           Inversion_Form1 = new ArrayList<>();
           Inversion_Form2 = new ArrayList<>();
           //初始化表1，因为表1中含跳表指针，所以要进行特判
           for(int i=0;i<arr1.length;i++){
               int skip = 0;
               //当当前位置等于跳表指针的整数*步长时
               if(skip1!= 0 && i%skip1==0 && i != arr1.length-1)
                   skip = skip1;//将该位置的跳表指针设置为跳表指针的步长
               t = new docID(arr1[i],skip);
               Inversion_Form1.add(t);
           }
           //表2同理
           for(int i=0;i<arr2.length;i++){
               int skip = 0;
               if(skip2!= 0 && i%skip2==0 && i != arr2.length-1)
                   skip = skip2;
               t = new docID(arr2[i],skip);
               Inversion_Form2.add(t);
           }
       }
   

   建立函数IntersectWithSkip，返回值为ArrayList<Integer>,为对应的合并后的表；

   首先先对一些基本数据进行存储，避免子函数调用影响程序运行速率，同时也为了代码的整体美观；

4.     public ArrayList<Integer> IntersectWithSkip(){
           ArrayList<Integer> answer =  new ArrayList<>();
           int p1 = 0;//表1的指针
           int p2 = 0;//表2的指针
           int size1 = Inversion_Form1.size();//记录下表1的长度
           int size2 = Inversion_Form2.size();//记录下表2的长度
   

   根据书上描述的算法，将代码进行基本实现：

   ①将几个基本的数据进行存储，避免子函数调用过程中出错，同时有利于代码的编写和阅读；

5.         while( p1 < size1 && p2 < size2 ){
               //为了避免类间子函数调用影响速率，在这里进行储存
               int doc1 = Inversion_Form1.get(p1).getDocID();//p1指向表1的文档序号
               int doc2 = Inversion_Form2.get(p2).getDocID();//p2指向表2的文档序号
               int skip1 = Inversion_Form1.get(p1).getHasSkip();//p1指向的表1的跳表指针
               int skip2 = Inversion_Form2.get(p2).getHasSkip();//p2指向的表2的跳表指针
   

   ②当doc1 == doc2 时，即p1指向的表1的文档序号

6.             //当p1指向的docID = p2指向的docID时,p1&p2均++；
               if(doc1 == doc2){
                   answer.add(doc1);
                   p1++;
                   p2++;
   

   ③当doc1 < doc2 时，当对应的doc1 < doc2时， 此时观察doc1是否有跳表指针，此时先不进行跳转，观察跳表后的doc1是否比doc2大

   -> 如果满足，跳完继续上述操作;

   -> 没有，单纯的p1++即可；

             }else if(doc1 < doc2){
                //此时观察doc1是否有跳表指针，此时先不进行跳转，观察跳表后的doc1是否比doc2大
                if(skip1 !=0 && Inversion_Form1.get(p1+skip1).getDocID() <= doc2){
                    while(skip1 !=0 && Inversion_Form1.get(p1+skip1).getDocID() <= doc2){
                        p1 = p1 + skip1;//指针进行跳转
                        skip1 = Inversion_Form1.get(p1).getHasSkip();
                    }
                    p1++;
                }else
                    p1++;

④ 当 doc1 > doc2 时，观察 doc2 是否有对应的跳表指针，与上述操作类似；最后返回参数 answer；

              }else{
                if(skip2 !=0 && Inversion_Form2.get(p2+skip2).getDocID() <= doc1){
                    while(skip2 !=0 && Inversion_Form2.get(p2+skip2).getDocID() <= doc1){
                        p2 = p2 + skip2;
                        skip2 = Inversion_Form2.get(p2).getHasSkip();
                    }
                    p2++;
                }else
                    p2++;
            }
        }
        return answer;
    }
}

1. 最终建立两个test,对两个样例进行检测:

2. public class TheThird{
       public static void test1(){
           int []arr1 = {3,5,9,15,24,39,60,68,75,81,84,89,92,96,97,100,115};
           int []arr2 = {3,5,96,99,100,101};
           int skip1 = 4;//跳表指针的间隔距离
           int skip2 = 0;
           SkipAnd skipAnd = new SkipAnd(arr1,arr2,skip1,skip2);//建立一个新类
           ArrayList<Integer> answer = skipAnd.IntersectWithSkip();
           for(int i=0;i<answer.size();i++){
               int t = answer.get(i);
               System.out.print(t + "->");
           }
       }
       public static void test2(){
           int []arr1 = {3,5,9,15,24,39,60,68,75,81,84,89,92,96,97,100,115};
           int []arr2 = {25,60,68,120,150};
           int skip1 = 4;
           int skip2 = 0;
           SkipAnd skipAnd = new SkipAnd(arr1,arr2,skip1,skip2);
           ArrayList<Integer> answer = skipAnd.IntersectWithSkip();
           for(int i=0;i<answer.size();i++){
               int t = answer.get(i);
               System.out.print(t + "->");
           }
       }
       public static void main(String []args){
           //test1();
           test2();
       }
   }
   

   (4)阅读教材《Introduction to Information Retrieval》第 42 页 Figure 2.12 中所描述的 邻近搜索（proximity search）中的两个倒排记录表（postings lists）的合并算法，并用 Java 语言或其他常用语言实现该算法，并按要求做适当改进。要求使用附件“HW2.txt”中的 60 个文档（每行表示一个 document，按空格切词，文档中的单词全部转换为小写）建立 positional index，两个词项之间的间距（注：相邻的两个词项的间距为 1）的形式包括以 下三种情形（x 是一个正整数）： “-x”、“+x”和“x”，

   其中，“-x”表示第一个词项在第二个词项的左侧且间隔在 x 之内，“+x”表示第一个 词项在第二个词项的右侧且间隔在 x 之内，“x”表示第一个词项与第二个词项的间隔（左 侧和右侧均可）在 x 之内。要求在以下例子上验证算法的正确性：(ranking, filtering, -3), (ranking, filtering, -5), (ranking, filtering, -4), (ranking, filtering, -7), (heterogeneous, learning, +3), (recommendation, bias, 2)。

   1.         因为要建立具体的位置索引，所以建立了四个类，分别为 Token 、 Documents 、 Position 、 和最终的主类；

      （ 1 ） Token 词项类含有 2 个参数，分别为： word 、 LocationIndex; 分别用来记录对应的词

      项和保存文档号以及对应的位置索引。

              其中函数 addIndex 主要是为了对应的文档编号下位置索引的添加；同时重新定义了toString 函数，使得类的输出变得简易；

      class Token{
          public  String word;//词项
          public HashMap<Integer,LinkedList<Integer>> LocationIndex;//记录词项的docID以及对应的
          public Token(String word){
              this.word = word;
              this.LocationIndex = new HashMap<>();
          }
          public void addIndex(int docID,LinkedList<Integer> Indexes){
              LocationIndex.put(docID,Indexes);//
          }
          public String toString(){
              String tmp = "";
              tmp += word + ":";
              for(int i: LocationIndex.keySet()){
                  tmp += i +":"+LocationIndex.get(i)+"  ";
              }
              return tmp;
          }
      }
      

      （2） Document 类

              该类是整个代码里最主要的类，包含对 HW2.txt 文件的读取以及每个文档的保存， 对每个文档进行词项分割后词项的保存，以及最终的检索；

              首先，Document 类涉及到保存操作，设置了两个参数对数据进行保存和读取，分别为 tokens 和 documentsWithID ，分别对读取到的词项以及对应的位置检索和文档进行保存；

      class Documents {
          HashMap<String,Token> tokens;//词项
          HashMap<Integer, String> documentsWithId;//保存文档以及编号
      

          进行构造函数的建立，在构造函数里对两个参数进行 new 操作，并读取文件，（因 为涉及到异常处理，所以写在 try 中），将每行文档拆解出来，放入对应的 domentsWithId 中；

          public Documents() {
              try {
                  this.documentsWithId = new HashMap<>();
                  this.tokens = new HashMap<>();
                  FileInputStream inFile = new FileInputStream("G:\\大二\\大二下\\信息检索\\HW2.txt");
                  BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inFile));
                  String str = null;
                  int lineNum = 0;
                  //读取文件；
                  while ((str = bufferedReader.readLine()) != null) {
                      //System.out.println(str);
                      lineNum++;
                      documentsWithId.put(lineNum, str);
                  }
                  //关闭文件
                  inFile.close();
                  bufferedReader.close();
              } catch (FileNotFoundException e) {
                  throw new RuntimeException(e);
              } catch (IOException e) {
                  throw new RuntimeException(e);
              }
              //检查文档读取结果
              for (Integer i : documentsWithId.keySet()) {
                  System.out.println(i + " " + documentsWithId.get(i));
              }
          }
      

              第二步就要进行词项的分割以及对应的位置索引的保存操作；首先按序号大小读取文 档，与此同时将文档给转化成小写，使用正则化分割操作，将每个文档分割成一个个的 token；

              对于每个文档中单词和该单词在文档中位置，采用 terms 进行存取；如果从未读到过该单词，就在 terms 中新建一个词项，并将刚刚遍历到的位置存取进去；如果曾经在这个文档中读取过，就将将刚刚遍历到的位置放进对应的 LinkedList 中；

          public void Partition(){
              for (Integer i : documentsWithId.keySet()) {
                  String str = documentsWithId.get(i).toLowerCase();//同时转化成小写
                  System.out.println(i+":"+str);
                  //使用一个HashMap数据结构对每一个文档中的word以及对应的位置进行存储；
                  HashMap<String,LinkedList<Integer>> terms =  new HashMap<>();
                  int index = 0;//单词在文档中的位置
                  //将每份文档提取出来，进行词项，并记录下每个词项在文档中的位置
                  for(String eval :str.split("\\s+|: |, |\n")){
                      index ++;
                      //如果从未到这个单词，就新建一个；
                      if(!terms.containsKey(eval)){
                          terms.put(eval,new LinkedList<Integer>());
                      }
                      //读取到了就把对应的位置放进去
                      terms.get(eval).add(index);
                  }
       
                  for(String eval: terms.keySet()){
                      System.out.println(eval+":"+terms.get(eval));
                  }
      

              当这个文档读取完成后，再将刚刚的 terms 进行遍历，观察 tokens 中是否读取过这 些单词，如果读取过，则将刚刚的文档编号以及文档编号对应下的位置索引存入 terms 对应单词下；如果未读取过，则新建一个，再进行读取；

                  for(String eval: terms.keySet()){
                      Token one = new Token(eval);
                      //当词项存储结构中不含对应的单词时,就新建一个对应的
                      if(tokens.isEmpty() || !tokens.containsKey(eval)){
                          tokens.put(eval,one);
                      }
                      tokens.get(eval).addIndex(i,terms.get(eval));
                  }
              }
              for(String eval: tokens.keySet()){
                  Token term = tokens.get(eval);
                  System.out.println(term);
              }
          }
      

              最后一个函数，就是对应的 k 词近邻搜索函数 Intersect；该函数传入参数有 4 个，分 别为两个单词，多少个词之内，以及左边右边还是两边都含；

              首先写出了左右都含的情况下的算法，在此基础上，如果第一个词只能在第二个词的 左边，则 answer 中只保存第一个词的位置小于第二个词的情况，否则，保存第一个词的位置大于第二个词的情况；最后对结果进行输出；

          public void Intersect(String p1,String p2,int k,int bias){
              ArrayList<Position> answer = new ArrayList<>();//存储答案的位置
              Token token1 = tokens.get(p1);
              Token token2 = tokens.get(p2);
              for(int i:token1.LocationIndex.keySet()){
                  int pp1 = 0;//token1位置索引中的指针
                  int pp2 = 0;//token2位置索引中的指针
                  //如果token2含有相等的文档Id，则进行查找，是否符合条件
                  if(token2.LocationIndex.containsKey(i)){
                      LinkedList<Integer> tokenList1 = token1.LocationIndex.get(i);//对应文档编号下的位置
                      LinkedList<Integer> tokenList2 = token2.LocationIndex.get(i);//对应文档编号下的位置
                      LinkedList<Integer> l = new LinkedList<>();
                      while(pp1 < tokenList1.size()){
                          while(pp2 < tokenList2.size()){
                              if (abs(tokenList1.get(pp1) - tokenList2.get(pp2) )<= k){
                                  l.add(tokenList2.get(pp2));
                              }else if(tokenList1.get(pp1) > tokenList2.get(pp2) ){
                                  break;
                              }
                              pp2++;
                          }
                          while(!l.isEmpty() && abs(l.get(0)-tokenList1.get(pp1))>k){
                              l.remove(0);
                          }
                          for (int eval:l){
                              int docId = i;
                              if (bias == 0)
                                  answer.add(new Position(docId,tokenList1.get(pp1),eval));
                              else if (bias == -1){
                                  if(tokenList1.get(pp1)<eval)
                                      answer.add(new Position(docId,tokenList1.get(pp1),eval));
                              }else{
                                  if(tokenList1.get(pp1)>eval)
                                      answer.add(new Position(docId,tokenList1.get(pp1),eval));
                              }
                          }
                          pp1++;
                      }
                  }
              }
              System.out.println("---------------------------------------");
              System.out.print("("+p1 + ","+ p2 + ",");
              if(bias < 0){
                  System.out.println(k*bias + ")");
              }else if (bias == 0){
                  System.out.println( k + ")");
              }else{
                  System.out.println("+"+ k + ")");
              }
              for(Position eval:answer){
                  System.out.println(eval);
              }
          }
      }
      

 (4)最后的主类，就是建立一个新类，对原函数进行调用即可

public class TheFourth {
    public static void test(){
        Documents mydoc = new Documents();
        mydoc.Partition();
        mydoc.Intersect("recommendation", "bias", 2,0);
        mydoc.Intersect("ranking", "filtering", 3,-1);
        mydoc.Intersect("ranking", "filtering", 5,-1);
        mydoc.Intersect("ranking", "filtering", 4,-1);
        mydoc.Intersect("ranking", "filtering", 7,-1);
        mydoc.Intersect("heterogeneous", "learning", 3,1);
    }
    public static void main(String []args){
        test();
    }
}

 （5）阅读教材《Introduction to Information Retrieval》第 59 页 Figure 3.5 中所描述的基于动态规划（dynamic programming）来计算两个字符串的编辑距离（edit distance）的算法，并用 Java 语言或其他常用语言实现该算法。

        建立 Distance 类，里面包含两个参数：字符串 1 和字符串 2：并建立构造函数对两个字符串进行初始化；

class Distance{
    String s1;//字符串1
    String s2;//字符串2
    public Distance(String s1,String s2){
        this.s1 = s1;
        this.s2 = s2;
    }

         在该类中建立函数 EditDistance。函数中建立矩阵 m，行数为第一个字符串长度+1，列 数为第二个字符串长度+1；

    public void EditDistance(){
        int [][] m= new int[s1.length()+1][s2.length()+1];

        对于第一行和第一列进行赋值，然后开始对于整个矩阵的赋值，有第二行开始，如果 对应的字符相等，则左上方的值+0；否则左上方值+1；因为要进行字符更改；同时，左边数字进行+1，表明进行 s2 进行了字符添加；上方数字进行+1，表明 s1 进行字符添加；

        for(int i=1;i<=s1.length();i++)
            m[i][0] =i;
        for (int j=1;j<=s2.length();j++)
            m[0][j]=j;
        for(int i=1;i<=s1.length();i++)
            for(int j = 1; j <= s2.length() ; j++){
                m[i][j] = min(m[i-1][j-1] + (s1.charAt(i-1)==s2.charAt(j-1)?0:1),m[i-1][j] + 1);
                m[i][j] = min(m[i][j],m[i][j-1]+1);
            }
        for(int i=0;i<=s1.length();i++)
        {
            for(int j = 0; j <= s2.length() ; j++){
                System.out.print(m[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println();
        System.out.println(s1 + " 和 "+s2 + "的编辑距离为"+m[s1.length()][s2.length()]);
        System.out.println("----------------------------------------------------");
    }
}

主程序进行测试：

public class TheFifth {
    public static void test1(){
        Distance myTerm = new Distance("business", "buissness");
        myTerm.EditDistance();
    }
    public static void test2(){
        Distance myTerm = new Distance("committee", "commmitee");
        myTerm.EditDistance();
    }
    public static void test3(){
        Distance myTerm = new Distance("conscious", "conncious");
        myTerm.EditDistance();
    }
    public static void test4(){
        Distance myTerm = new Distance("definitely", "definnately");
        myTerm.EditDistance();
    }
    public static void test5(){
        Distance myTerm = new Distance("fluorescent", "florescente");
        myTerm.EditDistance();
    }
    public static void test6(){
        Distance myTerm = new Distance("forty", "fourty");
        myTerm.EditDistance();
    }
    public static void test7(){
        Distance myTerm = new Distance("government", "govement");
        myTerm.EditDistance();
    }
    public static void test8(){
        Distance myTerm = new Distance("idiosyncrasy", "idiosyncracy");
        myTerm.EditDistance();
    }
    public static void test9(){
        Distance myTerm = new Distance("immediately", "immediatly");
        myTerm.EditDistance();
    }
    public static void test10(){
        Distance myTerm = new Distance("millennium", "milleniume");
        myTerm.EditDistance();
    }
    public static void test11(){
        Distance myTerm = new Distance("noticeable", "notisable");
        myTerm.EditDistance();
    }
    public static void test12(){
        Distance myTerm = new Distance("tendency", "tendance");
        myTerm.EditDistance();
    }
    public static void test13(){
        Distance myTerm = new Distance("truly", "truely");
        myTerm.EditDistance();
    }
    public static void test14(){
        Distance myTerm = new Distance("weird", "wierd");
        myTerm.EditDistance();
    }
    public static void test15(){
        Distance myTerm = new Distance("privilege", "privledge");
        myTerm.EditDistance();
    }
 
    public static void main(String []args){
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
        test8();
        test9();
        test10();
        test11();
        test12();
        test13();
        test14();
        test15();
    }
}

 计算得到的 15 组单词的编辑距离如下：

(business, buissness)：2

(committee, commmitee)：2

(conscious, conncious)：1

(definitely, definnately)：2

(fluorescent, florescente)：2

(forty, fourty)：1

(government, govement)：2

(idiosyncrasy, idiosyncracy)：1

(immediately, immediatly)：1

(millennium, milleniume)：2

(noticeable, notisable)：2

(tendency, tendance)：2

(truly, truely)：1

(weird, wierd)：2

(privilege, privledge)：2