substituter.java

代入法的启发示搜索 我的代码实现是：按照自然语言各字母出现频率的大小从高到低（已经有人作国统计分析了）先生成一张字母出现频率统计表（A）--------(e),(t,a,o,i,n,s,h,r),(

package ai;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2006</p>
 * <p>Company: </p>
 * @author srt
 * @version 1.0
 */

public class Substituter
    extends BaseDecipher {
  WordClass wc; //词库
  long start; //记录解密之前的系统时间
  long finish; //记录解密过程中某一个时刻的系统时间
  private char[] table; //已经经过统计的字母出现频率表（按从频率高到小排序）
  int[] statLetterResult; //数组中按密文字母的出现次数从高到低进行存放密文中的各个字母
  StringBuffer[] copyWord; //数组存放密文单词,重复单词不计入内,带*
  String[] word; //密文单词数组,重复单词不计入内
  int wordNum; //为密文单词总数,重复单词不计入内
  int[] match = new int[26];
  int label; //密文里的不同字母的个数
  int totalNumOfWord; //记录密文单词总数
  char[] change;

  Substituter() {
    wc = (WordClass) WordClass.getInstance();
    change = new char[26];
  }

  //初始化统计字母相对频率结果的数组
  private void initialStatLetterResult() {
    statLetterResult = new int[26];
    for (int i = 0; i <= 25; i++) {
      statLetterResult[i] = i;
    }
  }

  //交换数组中的两个元素
  private void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  //快速排序中的一个程序
  private int partition(int a[], int p, int r) {
    int i = p;
    int j = r + 1;
    int x = a[p];
    //将>=x的元素交换到左边区域
    //将<=x的元素交换到右边区域
    while (true) {
      while (a[++i] > x);
      while (a[--j] < x);
      if (i >= j) {
        break;
      }
      swap(a, i, j);
      swap(statLetterResult, i, j);
    }
    a[p] = a[j];
    a[j] = x;
    swap(statLetterResult, p, j);
    return j;
  }

//快速排序
  private void quickSort(int a[], int p, int r) {
    if (p < r) {
      int q = partition(a, p, r);
      quickSort(a, p, q - 1); //对左半段排序
      quickSort(a, q + 1, r); //对右半段排序
    }
  }

  //统计密文字母相对频率结果，存放在int[] statLetterResult，并按频率从大到小排序，
  //同时把密文里出现的不同字母个数总数存进lable,并把密文单词个数总数存进 totalNumOfWord
  private void statLetterFrequency() {
    initialStatLetterResult();
    int flagOfWord = 0; //单词结束标志位
    char contentIndex = ' '; //存放密文字符的临时变量
    int[] statLetterTemp = new int[26]; //存放26个字母的频率的数组，比如statLetterTemp[0]存放的是字母 a的出现频率
    for (int i = 0; i < sCiphertext.length(); i++) {
      contentIndex = sCiphertext.charAt(i); //读密文字符
      if ('a' <= contentIndex && contentIndex <= 'z') { //判断是否是小写字母？
        statLetterTemp[ (int) (contentIndex) - 97]++; //对相应字母的频率进行计数
        if (statLetterTemp[ (int) (contentIndex) - 97] == 1) {
          label++;
        }
        flagOfWord = 1; //单词标志位置1
      }
      else if ('A' <= contentIndex && contentIndex <= 'Z') { //判断是否是大写字母？
        statLetterTemp[ (int) (contentIndex) - 65]++; ////对相应字母的频率进行计数
        if (statLetterTemp[ (int) (contentIndex) - 65] == 1) {
          label++;
        }
        flagOfWord = 1;
      }
      else {
        if (flagOfWord == 1) {
          totalNumOfWord++; //记录密文单词个数
          flagOfWord = 0;
        }
      }
    }
    if (flagOfWord == 1) {
      totalNumOfWord++; //记录密文单词个数
    }
    //对数组进行从大到小排序，这里的排序算法是基于分治策略的排序算法，
    //是对《数据结构与算法设计》	王晓东 主编  电子工业出版社 第98页的算法作了些许修改
    quickSort(statLetterTemp, 0, 25);
  }

//判断S是否已经出现过了？如果之前已经出现过了，则返回1，否则，返回0
  private int isRepeated(String s, int length) {
    for (int i = 0; i < length; i++) {
      if (word[i].compareTo(s) == 0) {
        return 1;
      }
    }
    return 0;
  }

//初始化copyWord[]和word[],
  //word[]存放的是密文的单词（重复的单词只放一个，即密文里若出现are两次，都放在同一个word[i]里）
//copyWord[]存放的是与word[]相应的单词（用'*'替代真实字母）
  private void initialWordArray() {

    copyWord = new StringBuffer[totalNumOfWord]; //数组存放密文单词
    word = new String[totalNumOfWord]; //实际密文单词数组
    for (int i = 0; i < totalNumOfWord; i++) {
      copyWord[i] = new StringBuffer();
      word[i] = new String();
    }
    // int indexOfWord = 0;//记录存放word[]的索引
    int countOfWord = 0; //记录临时密文单词里的字母个数总数
    StringBuffer sbTemp = new StringBuffer(); //存放中间密文单词
    int flagOfWord = 0; //单词结束标志位
    char contentIndex = ' '; //存放密文字符的临时变量
    for (int i = 0; i < sCiphertext.length(); i++) {
      contentIndex = sCiphertext.charAt(i); //读密文字符
      if ('a' <= contentIndex && contentIndex <= 'z') { //判断是否是小写字母？
        sbTemp.append(contentIndex); //存储中间密文字母
        countOfWord++;
        flagOfWord = 1; //单词标志位置1
      }
      else if ('A' <= contentIndex && contentIndex <= 'Z') { //判断是否是大写字母？
        sbTemp.append( (char) (contentIndex + 32)); //存储中间密文字母
        countOfWord++;
        flagOfWord = 1;
      }
      else {
        if (flagOfWord == 1) {
          if (isRepeated(sbTemp.toString(), wordNum) == 0) {
            word[wordNum] = sbTemp.toString();
            for (int j = 0; j < countOfWord; j++) {
              copyWord[wordNum].append('*');
            }
            wordNum++;
          }
          sbTemp.delete(0, countOfWord); //把存放的临时中间明文单词清掉
          countOfWord = 0; //单词里的字母个数重新置0
          flagOfWord = 0;
        }
      }
    }
    if (flagOfWord == 1) {
      if (isRepeated(sbTemp.toString(), wordNum) == 0) {
        word[wordNum] = sbTemp.toString();
        for (int j = 0; j < countOfWord; j++) {
          copyWord[wordNum].append('*');
        }
        wordNum++;
      }
      sbTemp.delete(0, countOfWord); //把存放的临时中间明文单词清掉
      countOfWord = 0; //单词里的字母个数重新置0
      flagOfWord = 0;
    }
    //  System.out.println("密文单词总数,重复单词不计入内 wordNum " +wordNum);
    //System.out.println("密文里的不同字母的个数 lable " + lable);
    // for(int i = 0; i< wordNum; i++){
    //   System.out.print("word "+word[i]);
    //  System.out.println("对应的copyWord "+copyWord[i]);
    // }
  }

  //将gString放到词库中匹配(按长度进行,同时不是*号的字母要一致）
  private boolean tryToMatch(StringBuffer sb, char flag){
    //如果能找到所需要的单词，则返回相应单词
    String temp = wc.searchIsMatch1(sb.toString(), (int) flag,
                                    sb.length());
    int length = temp.length();
    if (length != 0) {
      wc.refreshWordOfSelected(temp, length); //对这个单词进行刷新，即结点的flag =0
      return true;
    }
    else
      return false;
  }

  private int callMatch(int frequent, int begin) {
    int i = 0, j, k;
    boolean test;
    char temp1;
    char temp2 = (char) (97 + statLetterResult[frequent]);
    for (j = 0; j < wordNum; j++) { //wordNum为单词总数,重复单词不计入内
      for (i = begin; i < 26; i++) {
        finish = System.currentTimeMillis();
        if ( (finish - start) >= 60000) {
          return -20; //时间超过，退出
        }
        temp1 = table[i];
        if ( (int) temp1 < 97) {
          continue;
        }
        test = changeString(copyWord[j], temp1, temp2, j);
        if (!test) {
          break;
        }
        test = tryToMatch(copyWord[j], temp1);
        if (test) {
          break;
        }
        else {
         refreshString(j, temp1);
          j = -1;
          begin = i + 1;
          break;
        }
      }
      if (i == 26 && j < wordNum){
        return -1;
      }
    }
    table[i] = (char) ( (int) table[i] - 30);
    return i;
  }

  //实现将*号的字母转换为指定的高频字母
  private boolean changeString(StringBuffer input, char changeChar,
                               char original, int locate) {
    boolean test = false;
    for (int i = 0; i < input.length(); i++)
      if (word[locate].charAt(i) == original) {
        input.setCharAt(i, changeChar);
        test = true;
      }
    return test;
  }

  //匹配错误,将转为*号的字母复原为原字母
  private void refreshString(int count, char wrong) {
    for (int j = 0; j <= count; j++) {
      for (int i = 0; i < copyWord[j].length(); i++) {
        if (copyWord[j].charAt(i) == wrong)
          copyWord[j].setCharAt(i, '*');
      }
    }
  }

//启发示搜索
  public int heuristicDecipher() {
    start = System.currentTimeMillis();
    char wrong = '0';
    int begin = 0;
    for (int i = 0; i < label; i++) {
      match[i] = callMatch(i, begin);
      if (match[i] == -20) {
        return 1; //超时
      }
      if (match[i] == -1) {
        if (i == 0) {
          return 0; //密文无法破解
        }
        table[match[i - 1]] = (char) ( (int) table[match[i - 1]] + 30);
        wrong = table[match[i - 1]];
        refreshString(wordNum - 1, wrong);
        begin = match[i - 1] + 1;
        i = i - 2;
      }
      else {
        wrong = '0';
        begin = 0;
      }
    }
    return 2; //正确
  }

  private void initialVar() {
    table = new char[] {
        'e', 't', 'a', 'o', 'i', 'n', 's', 'h', 'r', 'd', 'l', 'c', 'u', 'm',
        'w',
        'f', 'g', 'y', 'p', 'b', 'v', 'k', 'j', 'x', 'q', 'z'};
    label = 0;
    totalNumOfWord = 0;
    wordNum = 0;
    for (int i = 0; i < 26; i++) {
      match[i] = -1;
    }
  }

  public String displaySubTable() {
    StringBuffer sbResult = new StringBuffer();
    sbResult.append("密文：  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z\n");
    sbResult.append("明文：  ");
    for (int i = 0; i <= 25; i++) {
      sbResult.append( (char) (change[i]) + "  ");
    }
    return sbResult.toString();
  }

//调用子方法，实现解密
  public int decipher() {

    initialVar(); //初始化变量
    //统计密文字母相对频率结果，存放在int[] statLetterResult，并按频率从大到小排序，
    //同时把密文里出现的不同字母个数总数存进lable,并把密文单词个数总数存进 totalNumOfWord
    statLetterFrequency();
    //初始化copyWord[]和word[],
    //word[]存放的是密文的单词（重复的单词只放一个，即密文里若出现are两次，都放在同一个word[i]里）
    //copyWord[]存放的是与word[]相应的单词（用'*'替代真实字母）
    initialWordArray();
    //启发示搜索
    int temp = heuristicDecipher();
    if (temp == 0) {
      wc.refreshWordOfClass();//刷新词库，把在解密过程中用到的单词的FLAG重新置为0
      return 0; //密文无法解密
    }
    if (temp == 1) {
      wc.refreshWordOfClass();//刷新词库，把在解密过程中用到的单词的FLAG重新置为0
      return 1; //超时
    }

    for (int i = 0; i < 26; i++) {
      change[i] = (char) (i + 97);
    }
    for (int i = 0; i < label; i++) {
      //得出对应替换表，比如change[0]存放的是密文字母a所对应的明文字母
      change[statLetterResult[i]] = (char) ( (int) table[match[i]] + 30);
    }

    StringBuffer sbPlaintext = new StringBuffer(); //存放中间明文
    char contentIndex = ' '; //密文字符
    for (int i = 0; i < sCiphertext.length(); i++) {
      contentIndex = sCiphertext.charAt(i); //读密文字符
      if ('a' <= contentIndex && contentIndex <= 'z') { //判断是否是小写字母？
        sbPlaintext.append(change[ (int) contentIndex - 97]); //利用替换表把密文字母转换为明文字母
      }
      else if ('A' <= contentIndex && contentIndex <= 'Z') { //判断是否是大写字母？
        sbPlaintext.append(change[ (int) contentIndex - 65]); //利用替换表把密文字母转换为明文字母
      }
      else {
        sbPlaintext.append(contentIndex); //存储非字母的符号
      }
    }
    sPlaintext = sbPlaintext.toString(); //把最终结果传递给存储明文的字符串sPlaintext
    wc.refreshWordOfClass(); //刷新词库，把在解密过程中用到的单词的FLAG重新置为0
    return 2; //成功解密
  }
}