Java实现的最大匹配分词算法详解

本文实例讲述了Java实现的最大匹配分词算法。分享给大家供大家参考,具体如下:

全文检索有两个重要的过程:

1分词

2倒排索引

我们先看分词算法

目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词。 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词。这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度。用概率分词的好 处是不需要借助词典的帮助,坏处是算法比较麻烦,效率不高,也存在一定的出错率。

另外的一个方向是使用词典分词。就是事先为程序准备一个词典,然后通过这个词典对文章分词。目前较流行的方式有正向最大匹配算法和逆向最大匹配算法。逆向最大匹配算法在准确性上要更好一些。

以 “我是一个坏人” 为例,并最大词长为3,词库包含有 我、是、一、个、一个、坏人、大坏人

正向的顺序为

我是一
我是
我 ===> 得到一个词
是一个
是一
是 ===>得到一个词
一个坏
一个===> 得到一个词
坏人===>得到一个词

结果 我、是、一个、坏人

反向算法

个坏人
坏人==> 坏人
是一个
一个==> 一个
我是
是==> 是
我==> 我

结果 我、是、一个、坏人

java代码如下

package data;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
 * 最大匹配分词算法
 *
 * @author JYC506
 *
 */
public class SplitString {
 private Set<String> set = new HashSet<String>();
 private int positiveOver = 0;
 private int reverseOver = 0;
 /**
  * 正向最大匹配
  *
  * @param str 要分词的句子
  * @param num 词的最大长度
  * @return
  */
 public String[] positiveSplit(String str, int maxSize) {
  int tem = 0;
  int length = str.length();
  String[] ss = new String[length];
  char[] cc = str.toCharArray();
  for (int i = 0; i < length; i++) {
   positiveOver = 0;
   String sb = this.toStr(cc, i, maxSize);
   ss[tem++] = sb;
   i = i + positiveOver;
  }
  String[] ss2 = new String[tem];
  System.arraycopy(ss, 0, ss2, 0, tem);
  return ss2;
 }
 /**
  * 添加词库
  *
  * @param words
  */
 public void addWord(String[] words) {
  for (String st : words) {
   this.set.add(st);
  }
 }
 /**
  * 逆向最大匹配
  *
  * @param str
  * @param num
  * @return
  */
 public String[] reverseSplit(String str, int num) {
  int tem = 0;
  int length = str.length();
  String[] ss = new String[length];
  char[] cc = str.toCharArray();
  for (int i = str.length() - 1; i > -1; i--) {
   reverseOver = 0;
   String sb = this.toStr2(cc, i, num);
   tem++;
   ss[--length] = sb;
   i = i - reverseOver;
  }
  String[] ss2 = new String[tem];
  System.arraycopy(ss, str.length() - tem, ss2, 0, tem);
  return ss2;
 }
 private String toStr(char[] cs, int start, int num) {
  int num2 = num;
  out: for (int j = 0; j < num; j++) {
   StringBuffer sb = new StringBuffer();
   for (int i = 0; i < num2; i++) {
    if (start + i < cs.length) {
     sb.append(cs[start + i]);
    } else {
     num2--;
     j--;
     continue out;
    }
   }
   if (set.contains(sb.toString())) {
    positiveOver = num2 - 1;
    return sb.toString();
   }
   num2--;
  }
  return String.valueOf(cs[start]);
 }
 private String toStr2(char[] cs, int start, int num) {
  int num2 = num;
  for (int j = 0; j < num; j++) {
   StringBuffer sb = new StringBuffer();
   for (int i = 0; i < num2; i++) {
    int index = start - num2 + i + 1;
    if (index > -1) {
     sb.append(cs[index]);
    } else {
     num2--;
    }
   }
   if (set.contains(sb.toString())) {
    reverseOver = num2 - 1;
    return sb.toString();
   }
   num2--;
  }
  return String.valueOf(cs[start]);
 }
 public static void main(String[] args) {
  String[] words = new String[] { "我们", "我们五人", "五人一组", "一组" };
  SplitString ss = new SplitString();
  /*添加词到词库*/
  ss.addWord(words);
  String st = "我们五人一组";
  System.out.println("我们测试结果:");
  System.out.println("要分词的句子:" + st);
  /*使用两种方式分词,下面我指定最大词长度为4*/
  String[] ss2 = ss.reverseSplit(st, 4);
  String[] ss1 = ss.positiveSplit(st, 4);
  System.out.println("正向最大匹配分词算法分词结果:" + Arrays.toString(ss1));
  System.out.println("逆向最大匹配分词算法分词结果:" + Arrays.toString(ss2));
 }
}

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java字符与字符串操作技巧总结》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

时间: 2017-09-17

java中文分词之正向最大匹配法实例代码

前言 基于词典的正向最大匹配算法(最长词优先匹配),算法会根据词典文件自动调整最大长度,分词的好坏完全取决于词典. 所谓词典正向最大匹配就是将一段字符串进行分隔,其中分隔 的长度有限制,然后将分隔的子字符串与字典中的词进行匹配,如果匹配成功则进行下一轮匹配,直到所有字符串处理完毕,否则将子字符串从末尾去除一个字,再进行匹配,如此反复. 算法流程图如下: 下面给大家主要讲一下中文分词里面算法的简单实现,废话不多说了,现在先上代码 示例代码 package com; import java.util

Java文件上传下载、邮件收发实例代码

文件上传下载 前台: 1. 提交方式:post 2. 表单中有文件上传的表单项: <input type="file" /> 3. 指定表单类型: 默认类型:enctype="application/x-www-form-urlencoded" 文件上传类型:multipart/form-data FileUpload 文件上传功能开发中比较常用,apache也提供了文件上传组件! FileUpload组件: 1. 下载源码 2. 项目中引入jar文件

Java web含验证码及权限登录实例代码

所用到的开发工具为myeclipse10,MySQL数据库. 首先,在myeclipse中新建一个Java web项目. 项目的结构: 数据库结构: 下面将各个包中的代码粘贴出来. com.ningmeng.dao包 package com.ningmeng.dao; import java.sql.Connection; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.SQLExcept

Java编程实现轨迹压缩算法开放窗口实例代码

轨迹压缩算法 场景描述 给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,根据距离阈值压缩记录,将过滤后的所有记录的经纬度坐标构成一条轨迹 算法描述 这种算法的用处还是相当广泛的. 轨迹压缩算法分为两大类,分别是无损压缩和有损压缩,无损压缩算法主要包括哈夫曼编码,有损压缩算法又分为批处理方式和在线数据压缩方式,其中批处理方式又包括DP(Douglas-Peucker)算法.TD-TR(Top-Down Time-Ratio)算法和Bellman算法,在线数据压缩方式又包括滑动窗口.

Java 数据类型及类型转换的互相转换实例代码

一.基本数据类型 java的数据类型可以分为两大类:基本类型和复合类型. 基本类型:整型(int,short,long,byte).浮点型(float,double).布尔型(boolean).和字符型(char) 复合类型:数组,类,接口 1.整型 各种整型数据所占空间及数的范围 数据类型 所占内存空间/位 数的范围 byte 8 -128~127 short 16 -32768~32767 int 32 -2^31~2^31-1 long 64 -2^63~2^63-1 整型以补码的形式存放

java 实现计数排序和桶排序实例代码

java 实现计数排序和桶排序实例代码 目录 比较和非比较的区别 常见的快速排序.归并排序.堆排序.冒泡排序等属于比较排序.在排序的最终结果里,元素之间的次序依赖于它们之间的比较.每个数都必须和其他数进行比较,才能确定自己的位置. 在 冒泡排序 之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²).在 归并排序.快速排序 之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均 O(nlogn) . 比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布

java读取http请求中的body实例代码

在http请求中,有Header和Body之分,读取header使用request.getHeader("..."); 读取Body使用request.getReader(),但getReader获取的是BufferedReader,需要把它转换成字符串, 下面是转换的方法. public static String getBodyString(BufferedReader br) { String inputLine; String str = ""; try {

java 数值类型分秒时间格式化的实例代码

java 数值类型分秒时间格式化的实例代码 java 实例代码: import java.util.concurrent.TimeUnit; public class DateUtils { private static final String[] UNIT_DESC = new String[]{"天", "小时", "分钟", "秒"}; /** * 格式化持续时间<br/> * 将持续时间,格式化为 xx天

java多线程编程技术详解和实例代码

 java多线程编程技术详解和实例代码 1.   Java和他的API都可以使用并发. 可以指定程序包含不同的执行线程,每个线程都具有自己的方法调用堆栈和程序计数器,使得线程在与其他线程并发地执行能够共享程序范围内的资源,比如共享内存,这种能力被称为多线程编程(multithreading),在核心的C和C++语言中并不具备这种能力,尽管他们影响了JAVA的设计. 2.   线程的生命周期 新线程的生命周期从"新生"状态开始.程序启动线程前,线程一直是"新生"状态:

使用Java和WebSocket实现网页聊天室实例代码

在没介绍正文之前,先给大家介绍下websocket的背景和原理: 背景 在浏览器中通过http仅能实现单向的通信,comet可以一定程度上模拟双向通信,但效率较低,并需要服务器有较好的支持; flash中的socket和xmlsocket可以实现真正的双向通信,通过 flex ajax bridge,可以在javascript中使用这两项功能. 可以预见,如果websocket一旦在浏览器中得到实现,将会替代上面两项技术,得到广泛的使用.面对这种状况,HTML5定义了WebSocket协议,能更