文本文件单词的检索与计数

叁歲伎倆 2023-10-05 00:59 12阅读 0赞

### 文章目录 ###

*   *  一、实验任务
     *  二、实验要求
     *  三、文本中找子串的算法
     *   *  1. 简单模式匹配算法
         *  2.使用KMP算法

## 一、实验任务 ##

*  建立一个文本文件，统计给定单词在文本文件中出现的总次数及位置。

## 二、实验要求 ##

*  文本文件中每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写，统计给定单词在文本文件中出现的总次数，检索输出的某个单词出现在文本中的行号、在该行中出现的位置。
 *  设计数据量大的文本，进行子串的查询处理，分析算法运行的时间效率，对所有输出的匹配位置结果进行验证，以证明算法设计和实现的正确性。
 *  用朴素模式匹配算法或KMP算法实现字符串定位；可正确读取，保存文本。

## 三、文本中找子串的算法 ##

### 1. 简单模式匹配算法 ###

public static int index(String s,String t,int pos)  
\{  
int i=pos; int j=0;  
while(i<s.length()&&j<t.length())  
\{  
if(s.charAt(i)==t.charAt(j))  
\{  
i++;j++;  
\}  
else  
\{  
i=i-j+1;  
j=0;  
\}  
\}  
if(j>=t.length())  
\{  
return i-t.length();  
\}  
return -1;  
\}

*  从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。

### 2.使用KMP算法 ###

public static int kmp(String str,String dest){
        //计算部分匹配表
        int [] next=kmpnext(dest);
          System.out.println("next ="+Arrays.toString(next));
        //查找匹配位置
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            if(str.charAt(i) == dest.charAt(j)){
                j++;
            }
            if(j == dest.length()){
                return i-j+1;
            }
        }
        return -1;
    }
    
    /**
     * 计算部分匹配表
     */
    public static int[] kmpnext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
    
        for(int i = 1,j = 0; i < dest.length(); i++){
            while(j > 0 && dest.charAt(j) != dest.charAt(i)){
                j = next[j - 1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    }

*  假设主文本字符串为S，模式字符串为P，并假设现在S匹配的位置为i，P匹配的索引位置为j，初始时 i = 1 , j = 1,对S\[ i \]和P\[ j \]进行比对，如果S\[ i \] = P\[ j \]记做匹配成功，那么S和P的匹配位置向后移动一位( i++ , j++ )，继续比较；  
    如果S\[ i \] != P\[ j \]记做匹配失败，那么将i修改为此次匹配开始的位置的后一位，j重置为0（ i = i - j + 1 , i = 0 ），继续比较。
 *  第一趟匹配：i = 1 , j = 1 此时 S1 = P1。进行下一个字符的匹配 i++ , j++，此时 S2 != P2 终止第一趟匹配进行第二趟匹配。此时i回滚到上一次匹配开始的后一位 i = 2 ，j重置为0。
 *  第二趟匹配：i = 2 , j = 1 此时 S2 != P1。结束第二趟匹配，开始第三趟匹配。此时i回滚到上一次匹配开始的后一位 i = 3 ，j重置为1。
 *  第三趟匹配：i = 3 , j = 1 此时 S3 = P1 。进行下一个字符的匹配 i++ , j++，此时 S4 = P2 。进行下一个字符的匹配 i++ , j++ ，此时 S5 = P3 。进行下一个字符的匹配 i++ , j++ ,此时 S6 = P4。进行下一个字符的匹配 i++ , j++ ，此时 S7 = P5 。进行下一个字符的匹配 i++ , j++ ，此时 S8 = P6 。进行下一个字符的匹配 i++ , j++ ，此时 S9 != P7 终止第三趟匹配进行第四趟匹配。此时i回滚到上一次匹配开始的后一位 i = 4，j重置为1。
 *  第四趟匹配：i = 4 , j = 1 此时 S4 != P1。结束第四趟匹配，开始第五趟匹配。此时i回滚到上一次匹配开始的后一位 i = 5 ，j重置为1。
 *  第五趟匹配：i = 5 , j = 1 此时 S5 = P1 。进行下一个字符的匹配 i++ , j++ ，此时 S6 != P2 终止第五趟匹配进行第六趟匹配。此时i回滚到上一次匹配开始的后一位 i = 6 ，j重置为1。
 *  第六趟匹配：i = 6 , j = 1 此时 S6 = P1 。进行下一个字符的匹配 i++ , j++ ，此时 S7 = P2……… 进行下一个字符的匹配 i++ , j++ ，此时 S13 = P8 。找到模式串P在主文本串中的位置，终止程序返回P第一次出现的索引位置5。