caeser.java

1．凯撒密码的盲目搜索 2．凯撒密码的启发示搜索1 3．凯撒密码的启发示搜索2

package ai;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2006</p>
 * <p>Company: </p>
 * @author srt
 * @version 1.0
 */
import java.util.*;

public class Caeser extends BaseDecipher{
  WordClass wc;//词库
  int[] statLetterResult;//统计字母相对频率结果

  //构造函数
  Caeser() {
    wc = (WordClass) WordClass.getInstance();
    initialStatLetterResult();
  }

  //初始化统计字母相对频率结果的数组
  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); //对右半段排序
    }
  }

 //统计字母相对频率结果
  private void statLetterFrequency() {
    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]++;//对相应字母的频率进行计数
      }
      else if ('A' <= contentIndex && contentIndex <= 'Z') {//判断是否是大写字母？
        statLetterTemp[ (int) (contentIndex) - 65]++;////对相应字母的频率进行计数
      }
    }
    //对数组进行从大到小排序，这里的排序算法是基于分治策略的排序算法，
    //是对《数据结构与算法设计》	王晓东 主编  电子工业出版社 第98页的算法作了些许修改
    quickSort(statLetterTemp, 0,25);
  }

//盲目搜索
  private int blindDecipher(int key) {
    //String s = wc.searchIsMatch1("*ub*******",10);//模糊寻找是否存在指定的结点
    //System.out.println("s: "+s);
    //wc.refreshWordOfSelected("*ub*******",10);//把指定的那些结点的标志位重新置为0
    //wc.refreshWordOfClass();//把词库里所有的结点的标志位都置为0

    int charCount = 0;//单词的字母个数
    int flag = 1;//单词结束标志位
    int wrongWordCount = 0;//错误单词数
    int totalWordCount = 0;//总共单词数
    StringBuffer sbPlaintext = new StringBuffer();//存放中间明文
    StringBuffer sbTemp = new StringBuffer();//存放中间明文单词
    char contentIndex = ' ';//密文字符
    char cTemp;//转换出来的临时字符
    for (int i = 0; i < sCiphertext.length(); i++) {
      contentIndex = sCiphertext.charAt(i);//读密文字符
      if ('a' <= contentIndex && contentIndex <= 'z') {//判断是否是小写字母？
        cTemp = (char) ( (contentIndex - 97 - key + 26) % 26 + 97);//利用key转换出中间明文字母
        sbPlaintext.append(cTemp);//存储中间明文字母
        sbTemp.append(cTemp);//存储中间明文字母
        charCount++;//对单词里的字母个数进行计数
        flag = 1;//单词标志位置1
      }
      else if ('A' <= contentIndex && contentIndex <= 'Z') {//判断是否是大写字母？
        cTemp =  (char) ( (contentIndex - 65 - key + 26) % 26 + 97);//利用key转换出中间明文字母
        sbPlaintext.append(cTemp);//存储中间明文字母
        sbTemp.append(cTemp);//存储中间明文字母
        charCount++;//对单词里的字母个数进行计数
        flag = 1;//单词标志位置1
      }
      else {
        if (flag == 1) {//是否是一个完整的单词？
          if (wc.search(sbTemp.toString()) == 0) {
            //System.out.println("sbTemp: " + sbTemp.toString());
            wrongWordCount++;//无法匹配的单词的个数计数
          }
          flag = 0;//单词标志位置0
          totalWordCount++;//对密文里总共有几个单词进行计数
          sbTemp.delete(0, charCount);//把存放的临时中间明文单词清掉
          charCount = 0;//单词里的字母个数重新置0
        }
        if (totalWordCount >= 500 && wrongWordCount >= 10) {
          return 0;//无法成功解密，返回0
        }
        sbPlaintext.append(contentIndex);//存储非字母的字符
      }
    }

    //System.out.println(wrongWordCount + "  " + totalWordCount);
    //System.out.println( (double) (wrongWordCount) / (double) (totalWordCount));
    if ( ( (double) (wrongWordCount) / (double) (totalWordCount)) >= 0.05) {
      return 0;
    }
    sPlaintext = sbPlaintext.toString();//把最终结果传递给存储明文的字符串sPlaintext
    return 1;//成功解密，返回1
  }

  private int caculateKey(int i,int j)
  {
    return  (i - j + 26)%26;
  }
  //盲目搜索
  public int blindDecipher() {
    int i;
    String s = "";
    for (i = 0; i <= 25; i++) {
      if (blindDecipher(i) == 1) {
      key = i;
        return 1;
      }
    }
    return 0;
  }

  //启发式搜索1
  public int heuristicDecipher1() {
    statLetterFrequency();
    //字母被统计出现相对频率的一个数组，已经被统计学论证过的
    int[] a = {
        4, 19, 0, 14, 8, 13, 18, 7, 17, 3, 11, 2, 20, 12, 22, 5, 6, 24, 15, 1,
        21, 10, 9, 23, 16, 25};
    for (int i = 0; i <= 25; i++) {
      if (blindDecipher(caculateKey(statLetterResult[0], a[i])) == 1) {
        return 1;
      }
    }
    return 0;
  }

  //启发式搜索2
  public int heuristicDecipher2() {
    statLetterFrequency();
   //字母被统计出现相对频率的一个数组，已经被统计学论证过的
   for (int i = 0; i <= 25; i++) {
     if (blindDecipher(caculateKey(statLetterResult[i], 4)) == 1) {
       return 1;
     }
   }
   return 0;
  }

}