精华内容
下载资源
问答
  • 最近做的一个项目的一部分就是分词技术,在网上找到的技术也有很多,在这里hanlp和ansj技术进行代码展示以及结果展示 首先是hanlp技术对分词的使用: 1.下载hanlp的jar包(地址:...

    最近做的一个项目的一部分就是分词技术,在网上找到的技术也有很多,在这里对hanlp和ansj技术进行代码展示以及结果展示

    首先是hanlp技术对分词的使用:

    1.下载hanlp的jar包(地址:http://hanlp.linrunsoft.com/services.html

    2.创建一个测试的java project 新建一个test的测试类进行测试:(代码如下)

    package hanlp;
    import java.util.List;
    import com.hankcs.hanlp.HanLP;
    import com.hankcs.hanlp.seg.common.Term;
    import com.hankcs.hanlp.tokenizer.NLPTokenizer;
    import com.hankcs.hanlp.tokenizer.TraditionalChineseTokenizer;
    
    public class test {
        public static void main(String args[])
        {
            List<Term> termList = NLPTokenizer.segment("中国科学院计算技术研究所的宗成庆教授正在教授自然语言处理课程");
            System.out.println(termList);
    
        }
    
    }

    展示结果如下:

    其次介绍ansj技术对分词的解决办法:

    1.下载ansj的jar包( http://maven.ansj.org/org/ansj/

    代码如下:

    package AnsjTest;
    
    import java.util.List;
    
    import org.ansj.splitWord.analysis.IndexAnalysis;
    import org.ansj.splitWord.analysis.ToAnalysis;
    
    import com.hankcs.hanlp.seg.common.Term;
    import com.hankcs.hanlp.tokenizer.NLPTokenizer;
    
    public class test {
    
        public static void main(String args[])
        {
            String str="欢迎使用ansj_seg,(ansj中文分词)在这里如果你遇到什么问题都可以联系我.我一定尽我所能.帮助大家.ansj_seg更快,更准,更自由!";
            System.out.println(IndexAnalysis.parse(str));
            
        }
    }

     

    转载于:https://www.cnblogs.com/zhaochunhui/p/10641120.html

    展开全文
  • 一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树,AC...

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树,AC算法,WM算法等等。

    背景

    在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下

    for (String document : documents) {

    for (String filterWord : filterWords) {

    if (document.contains(filterWord)) {

    //process ...

    }

    }

    }

    如果文本的数量是n,过滤词的数量是k,那么复杂度为O(nk);如果关键词的数量较多,那么支行效率是非常低的。

    计算机科学中,Aho–Corasick算法是由AlfredV.Aho和MargaretJ.Corasick发明的字符串搜索算法,用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度,约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数,如果每个子串互相匹配(如字典为a,aa,aaa,aaaa,输入的字符串为aaaa),算法的时间复杂度会近似于匹配的二次函数。

    原理

    在一般的情况下,针对一个文本进行关键词匹配,在匹配的过程中要与每个关键词一一进行计算。也就是说,每与一个关键词进行匹配,都要重新从文档的开始到结束进行扫描。AC自动机的思想是,在开始时先通过词表,对以下三种情况进行缓存:

    按照字符转移成功进行跳转(success表)

    按照字符转移失败进行跳转(fail表)

    匹配成功输出表(output表)

    因此在匹配的过程中,无需从新从文档的开始进行匹配,而是通过缓存直接进行跳转,从而实现近似于线性的时间复杂度。

    构建

    构建的过程分三个步骤,分别对success表,fail表,output表进行构建。其中output表在构建sucess和fail表进行都进行了补充。fail表是一对一的,output表是一对多的。

    按照字符转移成功进行跳转(success表)

    sucess表实际就是一棵trie树,构建的方式和trie树是一样的,这里就不赘述。

    按照字符转移失败进行跳转(fail表)

    设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到,那就把失败指针指向root。使用广度优先搜索BFS,层次遍历节点来处理,每一个节点的失败路径。

    匹配成功输出表(output表)

    匹配

    举例说明,按顺序先后添加关键词he,she,,his,hers。在匹配ushers过程中。先构建三个表,如下图,实线是sucess表,虚线是fail表,结点后的单词是ourput表。

    ef93ff297155267e9ed02bb4e2bd9e53.png

    代码

    import java.util.*;

    /**

    */

    public class ACTrie {

    private Boolean failureStatesConstructed = false;

    //是否建立了failure表

    private Node root;

    //根结点

    public ACTrie() {

    this.root = new Node(true);

    }

    /**

    * 添加一个模式串

    * @param keyword

    */

    public void addKeyword(String keyword) {

    if (keyword == null || keyword.length() == 0) {

    return;

    }

    Node currentState = this.root;

    for (Character character : keyword.toCharArray()) {

    currentState = currentState.insert(character);

    }

    currentState.addEmit(keyword);

    }

    /**

    * 模式匹配

    *

    * @param text 待匹配的文本

    * @return 匹配到的模式串

    */

    public Collection parseText(String text) {

    checkForConstructedFailureStates();

    Node currentState = this.root;

    List collectedEmits = new ArrayList<>();

    for (int position = 0; position < text.length(); position++) {

    Character character = text.charAt(position);

    currentState = currentState.nextState(character);

    Collection emits = currentState.emit();

    if (emits == null || emits.isEmpty()) {

    continue;

    }

    for (String emit : emits) {

    collectedEmits.add(new Emit(position - emit.length() + 1, position, emit));

    }

    }

    return collectedEmits;

    }

    /**

    * 检查是否建立了failure表

    */

    private void checkForConstructedFailureStates() {

    if (!this.failureStatesConstructed) {

    constructFailureStates();

    }

    }

    /**

    * 建立failure表

    */

    private void constructFailureStates() {

    Queue queue = new LinkedList<>();

    // 第一步,将深度为1的节点的failure设为根节点

    //特殊处理:第二层要特殊处理,将这层中的节点的失败路径直接指向父节点(也就是根节点)。

    for (Node depthOneState : this.root.children()) {

    depthOneState.setFailure(this.root);

    queue.add(depthOneState);

    }

    this.failureStatesConstructed = true;

    // 第二步,为深度 > 1 的节点建立failure表,这是一个bfs 广度优先遍历

    /**

    * 构造失败指针的过程概括起来就一句话:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。

    * 然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到,那就把失败指针指向root。

    * 使用广度优先搜索BFS,层次遍历节点来处理,每一个节点的失败路径。

    */

    while (!queue.isEmpty()) {

    Node parentNode = queue.poll();

    for (Character transition : parentNode.getTransitions()) {

    Node childNode = parentNode.find(transition);

    queue.add(childNode);

    Node failNode = parentNode.getFailure().nextState(transition);

    childNode.setFailure(failNode);

    childNode.addEmit(failNode.emit());

    }

    }

    }

    private static class Node{

    private Map map;

    private List emits;

    //输出

    private Node failure;

    //失败中转

    private Boolean isRoot = false;

    //是否为根结点

    public Node(){

    map = new HashMap<>();

    emits = new ArrayList<>();

    }

    public Node(Boolean isRoot) {

    this();

    this.isRoot = isRoot;

    }

    public Node insert(Character character) {

    Node node = this.map.get(character);

    if (node == null) {

    node = new Node();

    map.put(character, node);

    }

    return node;

    }

    public void addEmit(String keyword) {

    emits.add(keyword);

    }

    public void addEmit(Collection keywords) {

    emits.addAll(keywords);

    }

    /**

    * success跳转

    * @param character

    * @return

    */

    public Node find(Character character) {

    return map.get(character);

    }

    /**

    * 跳转到下一个状态

    * @param transition 接受字符

    * @return 跳转结果

    */

    private Node nextState(Character transition) {

    Node state = this.find(transition);

    // 先按success跳转

    if (state != null) {

    return state;

    }

    //如果跳转到根结点还是失败,则返回根结点

    if (this.isRoot) {

    return this;

    }

    // 跳转失败的话,按failure跳转

    return this.failure.nextState(transition);

    }

    public Collection children() {

    return this.map.values();

    }

    public void setFailure(Node node) {

    failure = node;

    }

    public Node getFailure() {

    return failure;

    }

    public Set getTransitions() {

    return map.keySet();

    }

    public Collection emit() {

    return this.emits == null ? Collections.emptyList() : this.emits;

    }

    }

    private static class Emit{

    private final String keyword;

    //匹配到的模式串

    private final int start;

    private final int end;

    /**

    * 构造一个模式串匹配结果

    * @param start 起点

    * @param end 重点

    * @param keyword 模式串

    */

    public Emit(final int start, final int end, final String keyword) {

    this.start = start;

    this.end = end;

    this.keyword = keyword;

    }

    /**

    * 获取对应的模式串

    * @return 模式串

    */

    public String getKeyword() {

    return this.keyword;

    }

    @Override

    public String toString() {

    return super.toString() + "=" + this.keyword;

    }

    }

    public static void main(String[] args) {

    ACTrie trie = new ACTrie();

    trie.addKeyword("hers");

    trie.addKeyword("his");

    trie.addKeyword("she");

    trie.addKeyword("he");

    Collection emits = trie.parseText("ushers");

    for (Emit emit : emits) {

    System.out.println(emit.start + " " + emit.end + "\t" + emit.getKeyword());

    }

    }

    }

    总结

    以上就是本文关于多模字符串匹配算法原理及Java实现代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

    如有不足之处,欢迎留言指出。感谢朋友们对本站的支持。

    展开全文
  • java字符串比较

    2019-05-31 15:54:19
    经过数据的分析,最后有中文的名称采用分词的方法进行相似对比,英文的文本之间的相似度计算用的是余弦距离,先哈希过。下面是计算两个List的余弦距离。 英文字符进行相似度比较 package com.e100.hotelco...

    应该场景:
    有一批酒店的产品名字,名字不规则,有中文有英文也会有特殊符号,现需要按这个产品的名称将其对应到相应的房型上。这时就需要按字符进行比较。去匹配相似度最高的房型名称之上。经过对数据的分析,最后有中文的名称采用分词的方法进行相似对比,英文的文本之间的相似度计算用的是余弦距离,先哈希过。下面是计算两个List的余弦距离。

    英文字符进行相似度比较

    package com.e100.hotelcore.stringUtils;
    import java.util.ArrayList;  
    import java.util.HashMap;  
    import java.util.Iterator;  
    import java.util.Map;  
      
      
    public class EnStringCompare {  
      
        public static double getSimilarity(ArrayList<String> doc1, ArrayList<String> doc2) {  
            if (doc1 != null && doc1.size() > 0 && doc2 != null && doc2.size() > 0) {  
      
                Map<Long, int[]> AlgorithmMap = new HashMap<Long, int[]>();  
      
                for (int i = 0; i < doc1.size(); i++) {  
                    String d1 = doc1.get(i);  
                    long sIndex = hashId(d1);  
                    int[] fq = AlgorithmMap.get(sIndex);  
                    if (fq != null) {  
                        fq[0]++;  
                    } else {  
                        fq = new int[2];  
                        fq[0] = 1;  
                        fq[1] = 0;  
                        AlgorithmMap.put(sIndex, fq);  
                    }  
                }  
      
                for (int i = 0; i < doc2.size(); i++) {  
                    String d2 = doc2.get(i);  
                    long sIndex = hashId(d2);  
                    int[] fq = AlgorithmMap.get(sIndex);  
                    if (fq != null) {  
                        fq[1]++;  
                    } else {  
                        fq = new int[2];  
                        fq[0] = 0;  
                        fq[1] = 1;  
                        AlgorithmMap.put(sIndex, fq);  
                    }  
      
                }  
      
                Iterator<Long> iterator = AlgorithmMap.keySet().iterator();  
                double sqdoc1 = 0;  
                double sqdoc2 = 0;  
                double denominator = 0;  
                while (iterator.hasNext()) {  
                    int[] c = AlgorithmMap.get(iterator.next());  
                    denominator += c[0] * c[1];  
                    sqdoc1 += c[0] * c[0];  
                    sqdoc2 += c[1] * c[1];  
                }  
      
                return denominator / Math.sqrt(sqdoc1 * sqdoc2);  
            } else {  
                return 0;  
            }  
        }  
      
        public static long hashId(String s) {  
            long seed = 131; // 31 131 1313 13131 131313 etc.. BKDRHash   
            long hash = 0;  
            for (int i = 0; i < s.length(); i++) {  
                hash = (hash * seed) + s.charAt(i);  
            }  
            return hash;  
        }  
      
        public static void main(String[] args) {  
            ArrayList<String> t1 = new ArrayList<String>();  
            ArrayList<String> t2 = new ArrayList<String>(); 
            ArrayList<String> t3 = new ArrayList<String>(); 
            t1.add("double");  
            t1.add("or");
            t1.add("twin");
            t1.add("superior");
           
      
            t2.add("superior"); 
            t2.add("twin"); 
            t2.add("double"); 
             
            t3.add("superior");
            t3.add("suite");
            t3.add("standard");
            t3.add("zone");
            System.out.println(getSimilarity(t1, t2));
            System.out.println(getSimilarity(t1, t3));
        }  
    }  
    

    余弦相似度计算字符串相似率

    比较中文比较准确,英文区分大少写,按空格分词,空格的多少也会影响到相似度,所以上面的方法比较英文比较准确。

    1、pom.xml

    展示一些主要的jar包

    	<!--结合操作工具包-->
            <dependency>
                <groupId>org.apache.commons</groupId>
                <artifactId>commons-lang3</artifactId>
                <version>3.5</version>
            </dependency>
           <!--bean实体注解工具包-->
               <dependency>
                <groupId>org.projectlombok</groupId>
                <artifactId>lombok</artifactId>
            </dependency>
          <!--汉语言包,主要用于分词-->
            <dependency>
                <groupId>com.hankcs</groupId>
                <artifactId>hanlp</artifactId>
                <version>portable-1.6.5</version>
            </dependency>
    

    2、main方法

     public static void main(String[] args) {
    
        	String content1 = "run of the house";
    
        	String content2 = "1 bed presidential suite space zone";
        	String content3 = "Premier";
        	String content4 = "Superior";
        	
    		double score = CosineSimilarity.getSimilarity(content1, content2);
    		System.out.println("相似度:" + score);
    
    		score = CosineSimilarity.getSimilarity(content1, content3);
    		System.out.println("相似度:" + score);
    		score = CosineSimilarity.getSimilarity(content1, content4);
    		System.out.println("相似度:" + score);
    	}
    

    3、Tokenizer(分词工具类)

    	package com.e100.hotelcore.stringUtils;
    
    import com.hankcs.hanlp.HanLP;
    import com.hankcs.hanlp.seg.common.Term;
    import java.util.List;
    import java.util.stream.Collectors;
    
    
    /**
     * 中文分词工具类*/
    public class Tokenizer {
    	 /**
         * 分词*/
        public static List<Word> segment(String sentence) {
    
            //1、 采用HanLP中文自然语言处理中标准分词进行分词
            List<Term> termList = HanLP.segment(sentence);
    
            //上面控制台打印信息就是这里输出的
            System.out.println(termList.toString());
    
            //2、重新封装到Word对象中(term.word代表分词后的词语,term.nature代表改词的词性)
            return termList.stream().map(term -> new Word(term.word, term.nature.toString())).collect(Collectors.toList());
        }
    }
    
    

    4、Word(封装分词结果)

    package com.e100.hotelcore.stringUtils;
    import lombok.Data;
    
    import java.util.Objects;
    
    /**
     * 封装分词结果*/
    @Data
    public class Word implements Comparable {
    	
    	 // 词名
        private String name;
        public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    
    	// 词性
        private String pos;
    
        // 权重,用于词向量分析
        private Float weight;
    
        public Word(String name, String pos) {
            this.name = name;
            this.pos = pos;
        }
    
        @Override
        public int hashCode() {
            return Objects.hashCode(this.name);
        }
    
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Word other = (Word) obj;
            return Objects.equals(this.name, other.name);
        }
    
        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            if (name != null) {
                str.append(name);
            }
            if (pos != null) {
                str.append("/").append(pos);
            }
    
            return str.toString();
        }
    
        @Override
        public int compareTo(Object o) {
            if (this == o) {
                return 0;
            }
            if (this.name == null) {
                return -1;
            }
            if (o == null) {
                return 1;
            }
            if (!(o instanceof Word)) {
                return 1;
            }
            String t = ((Word) o).getName();
            if (t == null) {
                return 1;
            }
            return this.name.compareTo(t);
        }
    
    	public Float getWeight() {
    		return weight;
    	}
    
    	public void setWeight(Float weight) {
    		this.weight = weight;
    	}
    	
    }
    
    

    5、CosineSimilarity

    package com.e100.hotelcore.stringUtils;
    
    import org.apache.commons.lang3.StringUtils;
    import org.slf4j.Logger;
    import org.slf4j.LoggerFactory;
    import org.springframework.util.CollectionUtils;
    import java.math.BigDecimal;
    import java.util.*;
    import java.util.concurrent.ConcurrentHashMap;
    import java.util.concurrent.atomic.AtomicInteger;
    
    
    /**
     * 判定方式:余弦相似度,通过计算两个向量的夹角余弦值来评估他们的相似度 余弦夹角原理: 向量a=(x1,y1),向量b=(x2,y2)
     * similarity=a.b/|a|*|b| a.b=x1x2+y1y2
     * |a|=根号[(x1)^2+(y1)^2],|b|=根号[(x2)^2+(y2)^2]
     */
    
    public class CosineSimilarity {
    
    	protected static final Logger LOGGER = LoggerFactory.getLogger(CosineSimilarity.class);
    
    	/**
    	 * 1、计算两个字符串的相似度
    	 */
    	public static double getSimilarity(String text1, String text2) {
    
    		// 如果wei空,或者字符长度为0,则代表完全相同
    		if (StringUtils.isBlank(text1) && StringUtils.isBlank(text2)) {
    			return 1.0;
    		}
    		// 如果一个为0或者空,一个不为,那说明完全不相似
    		if (StringUtils.isBlank(text1) || StringUtils.isBlank(text2)) {
    			return 0.0;
    		}
    		// 这个代表如果两个字符串相等那当然返回1了(这个我为了让它也分词计算一下,所以注释掉了)
    //            if (text1.equalsIgnoreCase(text2)) {
    //                return 1.0;
    //            }
    		// 第一步:进行分词
    		List<Word> words1 = Tokenizer.segment(text1);
    		List<Word> words2 = Tokenizer.segment(text2);
    
    		return getSimilarity(words1, words2);
    	}
    
    	/**
    	 * 2、对于计算出的相似度保留小数点后六位
    	 */
    	public static double getSimilarity(List<Word> words1, List<Word> words2) {
    
    		double score = getSimilarityImpl(words1, words2);
    
    		// (int) (score * 1000000 + 0.5)其实代表保留小数点后六位
    		// ,因为1034234.213强制转换不就是1034234。对于强制转换添加0.5就等于四舍五入
    		score = (int) (score * 1000000 + 0.5) / (double) 1000000;
    
    		return score;
    	}
    	
    	/**
         * 文本相似度计算 判定方式:余弦相似度,通过计算两个向量的夹角余弦值来评估他们的相似度 余弦夹角原理: 向量a=(x1,y1),向量b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2
         * |a|=根号[(x1)^2+(y1)^2],|b|=根号[(x2)^2+(y2)^2]
         */
        public static double getSimilarityImpl(List<Word> words1, List<Word> words2) {
    
            // 向每一个Word对象的属性都注入weight(权重)属性值
            taggingWeightByFrequency(words1, words2);
    
            //第二步:计算词频
            //通过上一步让每个Word对象都有权重值,那么在封装到map中(key是词,value是该词出现的次数(即权重))
            Map<String, Float> weightMap1 = getFastSearchMap(words1);
            Map<String, Float> weightMap2 = getFastSearchMap(words2);
    
            //将所有词都装入set容器中
            Set<Word> words = new HashSet<>();
            words.addAll(words1);
            words.addAll(words2);
    
            AtomicFloat ab = new AtomicFloat();// a.b
            AtomicFloat aa = new AtomicFloat();// |a|的平方
            AtomicFloat bb = new AtomicFloat();// |b|的平方
    
            // 第三步:写出词频向量,后进行计算
            words.parallelStream().forEach(word -> {
                //看同一词在a、b两个集合出现的此次
                Float x1 = weightMap1.get(word.getName());
                Float x2 = weightMap2.get(word.getName());
                if (x1 != null && x2 != null) {
                    //x1x2
                    float oneOfTheDimension = x1 * x2;
                    //+
                    ab.addAndGet(oneOfTheDimension);
                }
                if (x1 != null) {
                    //(x1)^2
                    float oneOfTheDimension = x1 * x1;
                    //+
                    aa.addAndGet(oneOfTheDimension);
                }
                if (x2 != null) {
                    //(x2)^2
                    float oneOfTheDimension = x2 * x2;
                    //+
                    bb.addAndGet(oneOfTheDimension);
                }
            });
            //|a| 对aa开方
            double aaa = Math.sqrt(aa.doubleValue());
            //|b| 对bb开方
            double bbb = Math.sqrt(bb.doubleValue());
    
            //使用BigDecimal保证精确计算浮点数
            //double aabb = aaa * bbb;
            BigDecimal aabb = BigDecimal.valueOf(aaa).multiply(BigDecimal.valueOf(bbb));
    
            //similarity=a.b/|a|*|b|
            //divide参数说明:aabb被除数,9表示小数点后保留9位,最后一个表示用标准的四舍五入法
            double cos = BigDecimal.valueOf(ab.get()).divide(aabb, 9, BigDecimal.ROUND_HALF_UP).doubleValue();
            return cos;
        }
        
        /**
         * 向每一个Word对象的属性都注入weight(权重)属性值
         */
        protected static void taggingWeightByFrequency(List<Word> words1, List<Word> words2) {
            if (words1.get(0).getWeight() != null && words2.get(0).getWeight() != null) {
                return;
            }
            //词频统计(key是词,value是该词在这段句子中出现的次数)
            Map<String, AtomicInteger> frequency1 = getFrequency(words1);
            Map<String, AtomicInteger> frequency2 = getFrequency(words2);
    
            //如果是DEBUG模式输出词频统计信息
    //        if (LOGGER.isDebugEnabled()) {
    //            LOGGER.debug("词频统计1:\n{}", getWordsFrequencyString(frequency1));
    //            LOGGER.debug("词频统计2:\n{}", getWordsFrequencyString(frequency2));
    //        }
            // 标注权重(该词出现的次数)
            words1.parallelStream().forEach(word -> word.setWeight(frequency1.get(word.getName()).floatValue()));
            words2.parallelStream().forEach(word -> word.setWeight(frequency2.get(word.getName()).floatValue()));
        }
        /**
         * 统计词频
         * @return 词频统计图
         */
        private static Map<String, AtomicInteger> getFrequency(List<Word> words) {
    
            Map<String, AtomicInteger> freq = new HashMap<>();
            //这步很帅哦
            words.forEach(i -> freq.computeIfAbsent(i.getName(), k -> new AtomicInteger()).incrementAndGet());
            return freq;
        }
        /**
         * 输出:词频统计信息
         */
        private static String getWordsFrequencyString(Map<String, AtomicInteger> frequency) {
            StringBuilder str = new StringBuilder();
            if (frequency != null && !frequency.isEmpty()) {
                AtomicInteger integer = new AtomicInteger();
                frequency.entrySet().stream().sorted((a, b) -> b.getValue().get() - a.getValue().get()).forEach(
                        i -> str.append("\t").append(integer.incrementAndGet()).append("、").append(i.getKey()).append("=")
                                .append(i.getValue()).append("\n"));
            }
            str.setLength(str.length() - 1);
            return str.toString();
        }
        /**
         * 构造权重快速搜索容器
         */
        protected static Map<String, Float> getFastSearchMap(List<Word> words) {
            if (CollectionUtils.isEmpty(words)) {
                return Collections.emptyMap();
            }
            Map<String, Float> weightMap = new ConcurrentHashMap<>(words.size());
    
            words.parallelStream().forEach(i -> {
                if (i.getWeight() != null) {
                    weightMap.put(i.getName(), i.getWeight());
                } else {
                    LOGGER.error("no word weight info:" + i.getName());
                }
            });
            return weightMap;
        }
    }
    
    

    6、AtomicFloat原子类

    package com.e100.hotelcore.stringUtils;
    import java.util.concurrent.atomic.AtomicInteger;
    
    public class AtomicFloat extends Number{
    	private AtomicInteger bits;
    
        public AtomicFloat() {
            this(0f);
        }
    
        public AtomicFloat(float initialValue) {
            bits = new AtomicInteger(Float.floatToIntBits(initialValue));
        }
    
        //叠加
        public final float addAndGet(float delta) {
            float expect;
            float update;
            do {
                expect = get();
                update = expect + delta;
            } while (!this.compareAndSet(expect, update));
    
            return update;
        }
    
        public final float getAndAdd(float delta) {
            float expect;
            float update;
            do {
                expect = get();
                update = expect + delta;
            } while (!this.compareAndSet(expect, update));
    
            return expect;
        }
    
        public final float getAndDecrement() {
            return getAndAdd(-1);
        }
    
        public final float decrementAndGet() {
            return addAndGet(-1);
        }
    
        public final float getAndIncrement() {
            return getAndAdd(1);
        }
    
        public final float incrementAndGet() {
            return addAndGet(1);
        }
    
        public final float getAndSet(float newValue) {
            float expect;
            do {
                expect = get();
            } while (!this.compareAndSet(expect, newValue));
    
            return expect;
        }
    
        public final boolean compareAndSet(float expect, float update) {
            return bits.compareAndSet(Float.floatToIntBits(expect), Float.floatToIntBits(update));
        }
    
        public final void set(float newValue) {
            bits.set(Float.floatToIntBits(newValue));
        }
    
        public final float get() {
            return Float.intBitsToFloat(bits.get());
        }
    
        @Override
        public float floatValue() {
            return get();
        }
    
        @Override
        public double doubleValue() {
            return (double) floatValue();
        }
    
        @Override
        public int intValue() {
            return (int) get();
        }
    
        @Override
        public long longValue() {
            return (long) get();
        }
    
        @Override
        public String toString() {
            return Float.toString(get());
        }
    }
    
    

    7、总结

    把大致思路再捋一下:

    (1)先分词: 分词当然要按一定规则,不然随便分那也没有意义,那这里通过采用HanLP中文自然语言处理中标准分词进行分词。

    (2)统计词频: 就统计上面词出现的次数。

    (3)通过每一个词出现的次数,变成一个向量,通过向量公式计算相似率。

    展开全文
  • 中文分词的原理——正、逆向最大长度匹配法、处理未登录字符串(JAVA) 中文分词就是中文断句,这样能消除文字的部分歧义。除了基本的分词功能,为了消除歧义还可以进行更多的加工。中文分词可以分成如下几个子任务...

    中文分词的原理——正、逆向最大长度匹配法、处理未登录字符串(JAVA)


    中文分词就是对中文断句,这样能消除文字的部分歧义。除了基本的分词功能,为了消除歧义还可以进行更多的加工。中文分词可以分成如下几个子任务:

    • 分词:把输入的标题或者文本内容等分成词。
    • 词性标注(POS):给分出来的词标注上名词或动词等词性。词性标注可以部分消除词的歧义,例如“行”作为量词和作为形容词表示的意思不一样。
    • 语义标注:把每个词标注上语义编码。

    很多分词方法都借助词库。词库的来源是语料库或者词典,例如“人民日报语料库”或者《现代汉语大词典》。

    中文分词的两类方法:

    • 机械匹配的方法:例如正向最大长度匹配(Forward Maximum Match)的方法和逆向最大长度匹配(Reverse Maximum Matching)的方法。
    • 统计的方法:例如最大概率分词方法和最大熵的分词方法等。

    可以把输入文本预切分成句子。可以使用BreakIterator把文本分成句子。BreakIterator.getSentenceInstance返回按标点符号的边界切分句子的实例。简单的分成句子的方法是(jqrw002.java):

    import java.text.BreakIterator;
    import java.util.Locale;
    
    public class jqrw002 {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		String stringToExamine = "可那是什么啊?1946年,卡拉什尼科夫开始设计突击步枪。在这种半自动卡宾枪的基础上设计出一种全自动步枪,并送去参加国家靶场选型试验。样枪称之为AK-46,即1946年式自动步枪。";
    
    		//根据中文标点符号切分
    		BreakIterator boundary = BreakIterator.getSentenceInstance(Locale.CHINESE); 
    		//设置要处理的文本
    		boundary.setText(stringToExamine);
    		int start = boundary.first();       //开始位置
    		for (int end = boundary.next(); end != BreakIterator.DONE;
    		    start = end, end = boundary.next()) {
    			//输出子串,也就是一个句子
    			System.out.println(stringToExamine.substring(start, end)); 
    		}
    
    	}
    
    }
    

    所得结果图为:
    在这里插入图片描述

    可以模仿BreakIterator,把分词接口设计成从前往后迭代访问的风格。通过调用next方法返回下一个切分位置。

    public class Segmenter {
    	public int next () {     //得到下一个词,如果没有则返回-1
    		// 返回最长匹配词,如果没有匹配上,则按单字切分
    	}
    }
    

    或者直接返回下一个词:

    Segmenter seg = new Segmenter("大学生活动中心");     //切分文本
    String word;
    do {
    	word = seg.nextWord();                      //返回一个词
    	System.out.println(word);
    } while (word != null);
    

    1.正向最大长度匹配法

    假如要切分“印度尼西亚地震”这句话,希望切分出“印度尼西亚”,而不希望切分出“印度”这个词。正向找最长词是正向最大长度匹配的思想。倾向于写更短的词,除非必要,才用长词表述,所以倾向切分出长词。

    正向最大长度匹配的分词方法实现起来很简单。每次从词典找和待匹配串前缀最长匹配的词,如果找到匹配词,则把这个词作为切分词,待匹配串减去该词,如果词典中没有词匹配上,则按单字切分。例如,Trie树结构的词典中包括如下的8个词语:

    大 大学 大学生 活动 生活 中 中心 心

    输入:“大学生活动中心”,首先匹配出开头的最长词“大学生”,然后匹配出“活动”,最后匹配出“中心”。切分过程如下图:
    在这里插入图片描述

    最后分词结果为:“大学生/活动/中心”。

    在分词类Segmenter的构造方法中输入要处理的文本。然后通过nextWord方法遍历单词。有个text变量记录切分文本。offset变量记录已经切分到哪里。分词类基本实现如下:

    public class Segmenter {
    	String text = null;     //切分文本
    	int offset;            //已经处理到的位置
    
    	public Segmenter(String text) {
    		this.text = text;   //更新待切分的文本
    		offset = 0;       //重置已经处理到的位置
    	}
    
    	public String nextWord() {             //得到下一个词,如果没有则返回null
    		// 返回最长匹配词,如果没有匹配上,则按单字切分
    	}
    }
    

    为了避免重复加载词典,在这个类的静态方法中加载词典:

    private static TSTNode root;      //根节点是静态的
    
    static {                           //加载词典
    	String fileName = "SDIC.txt";   //词典文件名
    	try {
    		FileReader fileRead = new FileReader(fileName);
    		BufferedReader read = new BufferedReader(fileRead);
    		String line;   //读入的一行
    		try {
    			while ((line = read.readLine()) != null) {    //按行读
    				StringTokenizer st = new StringTokenizer(line, "\t");
    				String key = st.nextToken(); //得到词
    				TSTNode endNode = createNode(key);  //创建词对应的结束节点并返回
    				//设置这个节点对应的值,也就是把它标记成可以结束的节点
    				endNode.nodeValue = key;
    			}
    		} catch (IOException e) {
    			e.printStackTrace();
    		}finally {
    			read.close(); //关闭读入流
    		}
    	} catch (FileNotFoundException e) {
    		e.printStackTrace();
    	} catch (IOException e) {
    		e.printStackTrace();
    	}
    }
    

    ​ 为了形成平衡的Trie树,把词典中的词先排序,排序后为:

    ​ 中 中心 大 大学 大学生 心 活动 生活

    ​ 按平衡方式生成的词典Trie树如下图所示,其中双圈表示的节点可以做为匹配终止节点:
    在这里插入图片描述

    在最大长度匹配的分词方法中,需要用到从待切分字符串返回从指定位置(offset)开始的最长匹配词的方法。例如,当输入串是“大学生活动中心”,则返回“大学生”这个词,而不是返回“大”或者“大学”。匹配的过程就好像一条蛇爬上一棵树。例如当offset=0时,找最长匹配词的过程如下图所示:
    在这里插入图片描述
    从Trie树搜索最长匹配单词的方法如下:

    public String nextWord() {     //得到下一个词
    	String word = null;
    	if (text == null || root == null) {
    		return word;
    	}
    	if (offset >= text.length()) //已经处理完毕
    		return word;
    	TSTNode currentNode = root; //从根节点开始
    	int charIndex = offset; //待切分字符串的处理开始位置
    	while (true) {
    		if (currentNode == null) {   //已经匹配完毕
    			if(word==null){  //没有匹配上,则按单字切分
    				word = text.substring(offset,offset+1);
    				offset++;
    			}
    			return word;  //返回找到的词
    		}
    		int charComp = text.charAt(charIndex) - currentNode.splitChar; //比较两个字符
    
    		if (charComp == 0) {
    			charIndex++; //找字符串中的下一个字符
    
    			if (currentNode.nodeValue != null) {
    				word = currentNode.nodeValue; // 候选最长匹配词
    				offset = charIndex;
    			}
    			if (charIndex == text.length()) {
    				return word; // 已经匹配完
    			}
    			currentNode = currentNode.mid;
    		} else if (charComp < 0) {
    			currentNode = currentNode.left;
    		} else {
    			currentNode = currentNode.right;
    		}
    	}
    }
    

    测试分词:

    Segmenter seg = new Segmenter("大学生活动中心"); //切分文本
    String word; //保存词
    do {
    	word = seg.nextWord(); //返回一个词
    	System.out.println(word);  //输出单词
    } while (word != null); //直到没有词
    

    可以给定一个字符串,枚举出所有的匹配点。以“大学生活动中心”为例,第一次调用时,offset是0,第二次调用时,offset是3。因为采用了Trie树结构查找单词,所以和用HashMap查找单词的方式比较起来,这种实现方法代码更简单,而且切分速度更快。

    正向最大长度切分方法虽然容易实现,但是精度不高。以“有意见分歧”这句话为例,正向最大长度切分的结果是:“有意/见/分歧”,逆向最大长度切分的结果是:“有/意见/分歧”。因为汉语的主干成分后置,所以逆向最大长度切分的精确度稍高。另外一种最少切分的方法是使每一句中切出的词数最小。

    正向最大长度匹配法代码示例(jqrw005.java):

    import java.util.ArrayList;
    import java.util.List;
    
    public class jqrw005 extends TernarySearchTrie {
    
        private int matchEnglish(int start, String sentence) {
            int i = start;
            for (; i < sentence.length();) {
                char c = sentence.charAt(i);
                if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
                    ++i;
                } else {
                    break;
                }
            }
            return i;
        }
        
        private int matchNum(int start, String sentence) {
            int i = start;
            for (; i < sentence.length();) {
                char c = sentence.charAt(i);
                if (c >= '0' && c <= '9') {
                    ++i;
                } else {
                    break;
                }
            }
            return i;
        }
        
        public List<String> tag(String sentence){
            List<String> words = new ArrayList<String>();
            for (int i = 0; i < sentence.length();) {
                String w = maxMatch(sentence, i);
                if (!"".equals(w)) {
                    words.add(w);
                    i += w.length();
                } else {
                    words.add(sentence.substring(i, i + 1));
                    i++;
                }
            }
            return words;
        }
        
        /**
         * 正向最大长度匹配
         * @param sentence
         * @param offset
         * @return
         */
        public String maxMatch(String sentence, int offset) {
            String ret = "";
            if (sentence == null || rootNode == null || "".equals(sentence)) {
                return "";
            }
            int endIndex = matchEnglish(offset, sentence);
            if (endIndex != offset) {
                return sentence.substring(offset,endIndex);
            }
    
            endIndex = matchNum(offset, sentence);
            if (endIndex != offset) {
                return sentence.substring(offset,endIndex);
            }
    
            TSTNode currentNode = rootNode;
            int charIndex = offset;
            while (currentNode != null) {
                
                int charComp = sentence.charAt(charIndex) - currentNode.splitchar;
                if (charComp == 0) {
                    charIndex++;
                    if(currentNode.data != null){
                        ret = currentNode.data;
                    }
                    if (charIndex == sentence.length()) {
                        return ret;
                    }
                    currentNode = currentNode.eqNode;
                } else if (charComp < 0) {
                    currentNode = currentNode.loNode;
                } else {
                    currentNode = currentNode.hiNode;
                }
            }
            return ret;
        }
        
        
        public static void main(String[] args) {
            jqrw005 tree=new jqrw005();
            tree.addWord("大学生").data="大学生";
            tree.addWord("大学").data="大学";
            tree.addWord("活动").data="活动";
            tree.addWord("中心").data="中心";
            
            List<String> ret =tree.tag("大学生活动中心");
            for (int i = 0; i < ret.size(); i++) {
                System.out.println(ret.get(i));
            }
        }
    
    }
    

    其中TernarySearchTrie的示例如下(TernarySearchTrie.java):

    public class TernarySearchTrie {
        public final class TSTNode {
            /**
             * 节点的值,词原文,词性,词频等
             */
            public String data = null;
            /**
             * 低节点
             */
            protected TSTNode loNode;
            /**
             * 相等节点
             */
            protected TSTNode eqNode;
            /**
             * 高节点
             */
            protected TSTNode hiNode;
            
            /**
             * 节点的字符
             */
            protected char splitchar;
    
            /**
             * 构造方法
             * 
             * @param splitchar
             *            该节点表示的字符
             */
            protected TSTNode(char splitchar) {
                this.splitchar = splitchar;
            }
    
            public String toString() {
                return "splitchar:" + splitchar;
            }
        }
    
        protected TSTNode rootNode;
        
        /**
         * 查询
         * @param word 要查询的单词
         * @return 未找到返回null,找到返回单词的结束节点
         */
        protected TSTNode getNode(String word) {
            if (null == word) {
                return null;
            }
            int len = word.length();
            if (len == 0)
                return null;
            TSTNode currentNode = rootNode; // 匹配过程中的当前节点的位置
            int charIndex = 0; // 表示当前要比较的字符在Key中的位置
            char cmpChar = word.charAt(charIndex);
            int charComp;
            while (true) {
                if (currentNode == null) {// 没找到
                    return null;
                }
                charComp = cmpChar - currentNode.splitchar;
                if (charComp == 0) {//相等往下走
                    charIndex++;
                    if (charIndex == len) {//找到了
                        return currentNode;
                    } else {
                        cmpChar = word.charAt(charIndex);//词往下走
                    }
                    currentNode = currentNode.eqNode;
                } else if (charComp < 0) {//小于往左走
                    currentNode = currentNode.loNode;
                } else {//大于往右走
                    currentNode = currentNode.hiNode;
                }
            }
        }
    
        /**
         * 向词典添加单词
         * @param word 单词
         * @return 单词的结束节点
         */
        protected TSTNode addWord(String word) {
            if (null == word) {
                throw new NullPointerException("空指针异常");
            }
            int charIndex = 0;
            if (null == rootNode) {
                rootNode = new TSTNode(word.charAt(0));
            }
            TSTNode currentNode = rootNode;
            while (true) {
                int charComp = word.charAt(charIndex) - currentNode.splitchar;
                if (charComp == 0) {
                    charIndex++;
                    if (charIndex == word.length()) {
                        return currentNode;
                    }
                    if (null == currentNode.eqNode) {
                        currentNode.eqNode = new TSTNode(word.charAt(charIndex));
                    }
                    currentNode = currentNode.eqNode;
                } else if (charComp < 0) {
                    if (null == currentNode.loNode) {
                        currentNode.loNode = new TSTNode(word.charAt(charIndex));
                    }
                    currentNode = currentNode.loNode;
                } else {
                    if (null == currentNode.hiNode) {
                        currentNode.hiNode = new TSTNode(word.charAt(charIndex));
                    }
                    currentNode = currentNode.hiNode;
                }
            }
    
        }
    }
    

    运行结果示意图:
    在这里插入图片描述

    2.逆向最大长度匹配法

    ​ 逆向最大长度匹配法英文叫做Reverse Directional Maximum Matching Method,或者Backward Maximum Matching Method。

    ​ 从输入串的最后一个字往前匹配词典。输入:“大学生活动中心”,首先匹配出“中心”,然后匹配出“活动”,最后匹配出“大学生”。切分过程如下图:
    在这里插入图片描述

    ​ 正向最大长度匹配使用标准Trie树,又叫做前缀树(prefix tree)。逆向最大长度匹配法使用中文后缀树(Suffix tree)。因为匹配待切分字符串的时候是从后往前匹配,所以词典树中,最后一个字符放在树的第一层。例如,[大学生]这个词,[生]放在树的第一层。把词倒挂到Trie树上,如下图所示。
    在这里插入图片描述

    ​ 从后往前,逐字增加一个词到后缀树。例如“大学生”这个词,首先增加“生”这个字,然后增加“学”这个字,最后增加“大”这个字。首先看下如何从后往前输出一个单词。

    String input = "大学生";
    for (int i = input.length() - 1; i >= 0; i--){     //从最后一个字开始遍历
        System.out.println(input.charAt(i));
    }
    

    后缀树的creatTSTNode方法实现如下:

    //在后缀树上创建key对应的节点,输入的词仍然是正常顺序
    public TSTNode creatTSTNode(char[] key, int keyLength){
    	int charIndex = keyLength - 1;     //从key的最后一个字符开始作为当前字符放入Trie树
    	char currentChar = key[charIndex];    //当前字符
    	if (rootNode == null) {            //创建根节点
    		rootNode = new TSTNode(currentChar);
    	}
    
    	TSTNode currentNode = rootNode;   //当前节点
    	while (true) {
    		//比较输入词中的当前字符与当前节点中的分隔字符
    		int charComp = currentChar - currentNode.splitChar;
    		if (charComp == 0) {
    			charIndex--;        //更新位置
    			if (charIndex < 0) {       //判断是否已经到头了
    				return currentNode;  //创建完毕,退出循环
    			}
    			currentChar = key[charIndex]; //更新当前字符
    			if (currentNode.mid == null) {  //向下的孩子不存在,创建它
    				//创建当前字符对应的节点
    				currentNode.mid = new TSTNode(currentChar);
    			}
    			currentNode = currentNode.mid;  //往下
    		} else if (charComp < 0) {
    			if (currentNode.left == null) {  //创建当前字符对应的节点
    				currentNode.left = new TSTNode(currentChar);
    			}
    			currentNode = currentNode.left; //当前节点转移到当前字符对应的节点
    		} else {
    			if (currentNode.right == null) { //创建当前字符对应的节点
    				currentNode.right = new TSTNode(currentChar);
    			}
    			currentNode = currentNode.right; //当前节点转移到当前字符对应的节点
    		}
    	}
    }
    

    ​ “上海自来水来自海上”“山东落花生花落东山”正序放和逆序放都一样。这两个字符串顺序是对称的。

    ​ 逆Trie树词典和正向的Trie树词典的creatTSTNode代码也是对称的。字符位置charIndex–和charIndex++是对称的。词的开始位置和结束位置也是对称的。

    ​ 如果词典中有“心中”和“中”两个词,那么在三叉trie树中“中”那个节点下要放两个值?“心中”这个值不作为“中”这个节点的值,而是作为“心”这个节点的值,“心”这个节点是节点“中”的子节点:

    dic.addWord("心中","中心");
    dic.addWord("中","中");
    

    词典内部的处理方式和addWord的参数个数无关。dic.addWord(Sring word){} 这样定义方法就可以了,不需要两个参数。增加一个词的调用方法正确写法如下:

    dic.addWord("中心");
    

    ​ 匹配的时候是从后往前匹配。匹配“大学生活动中心”,先找到[心]这个字符,然后再找到[中]。直到树走到头了,或者遍历完整个句子才返回。

    ​ 逆向最大长度匹配中查找词典的方法:

    public char[] matchLong(char[] key, int start) {  //输入字符串和匹配的开始位置
    	char[] ret = null;
    
    	int numEnd = matchNum(start, key);    //看能否找到数字串
    	if (numEnd < start) {                  //找到了数字串
    		char[] num = new char[start - numEnd];
    		System.arraycopy(key, numEnd + 1, num, 0, num.length);
    		return num;
    	}
    
    	int englishEnd = matchEnglish(start, key); //看能否找到英文串
    	if (englishEnd < start) { 	             //找到了英文单词串
    		char[] english = new char[start - englishEnd];
    		System.arraycopy(key, englishEnd + 1, english, 0, english.length);
    		return english;
    	}
    
    	TSTNode currentNode = rootNode;
    	int charIndex = start; //从字符串的后面往前找
    	while (true) {
    		if (currentNode == null) {        //树走到头了
    			return ret;
    		}
    		int charComp = key[charIndex] - currentNode.spliter;
    
    		if (charComp == 0) {
    			charIndex--;
    
    			if (currentNode.data != null) {
    				ret = currentNode.data;   // 候选最长匹配词
    			}
    			if (charIndex < 0) {           //遍历完整个句子了
    				return ret;               //已经匹配完
    			}
    			currentNode = currentNode.eqNode;
    		} else if (charComp < 0) {
    			currentNode = currentNode.loNode;
    		} else {
    			currentNode = currentNode.hiNode;
    		}
    	}
    }
    

    测试查找词的方法:

    String sentence = "大学生活动中心";
    int offset = sentence.length()-1;                        //从句子的最后一个位置开始往前匹配
    char[] ret = dic.matchLong(sentence.toCharArray(), offset);
    System.out.print(sentence+" match:"+String.valueOf(ret)); //输出匹配结果:中心
    

    计算树中所有节点的数量:

    protected int numNodes() {                     //返回树中的节点总数
    	return recursiveNodeCalculator(rootNode, 0);
    }
    
    /**
     *  递归的方式访问每个节点,计算节点数量
     *
     *@param  currentNode  当前节点
     *@param  numNodes2    目前为止节点的数量
     *@return              本节点及以下节点的节点数量
     */
    private int recursiveNodeCalculator(TSTNode currentNode, int numNodes2) {
    	if (currentNode == null) {
    		return numNodes2;
    	}
    	//输入当前节点数numNodes2,返回新的节点数numNodes
    	int numNodes = recursiveNodeCalculator(currentNode.left, numNodes2);
    	//输入当前节点数numNodes,返回新的节点数numNodes
    	numNodes =	recursiveNodeCalculator(currentNode.mid, numNodes);
    	//输入当前节点数numNodes,返回新的节点数numNodes
    	numNodes =	recursiveNodeCalculator(currentNode.right, numNodes);
    	numNodes++;
    	return numNodes;
    }
    

    测试计算节点数量的方法:

    String dicFile = "SDIC.txt"; //中文单词文件
    TernarySearchTrie dic=new TernarySearchTrie(dicFile); //根据词典构建Trie树
    System.out.print(dic.numNodes()); //输出55893
    

    ​ 所有的中文单词用逆向方式存储需要55893个节点,用正向方式存储需要55109个节点。词尾用字比较分散,词首用字比较集中。

    如果不考虑相等子的节点数,只计算首节点数:

    protected int headNodes() {
    	return recursiveHeadNode(root, 0);
    }
    
    private int recursiveHeadNode(TSTNode currentNode, int numNodes2) {
    	if (currentNode == null) {
    		return numNodes2;
    	}
    	int numNodes = recursiveHeadNode(currentNode.left, numNodes2);
    	numNodes = recursiveHeadNode(currentNode.right, numNodes);
    	numNodes++;
    	return numNodes;
    }
    

    逆向Trie树首节点数4029。正向Trie树首节点数4092。词的尾字意义更专一,有更好的消除歧义效果。

    在电影《本杰明.巴顿传》中,时间逆转后,在前线阵亡的士兵可以重新返回家乡。逆向做事情,有时候有意向不到的好处。例如:“有意见分歧”这句话,正向最大长度切分的结果是:“有意/见/分歧”,逆向最大长度切分的结果是:“有/意见/分歧”。因为汉语的主干成分后置,所以逆向最大长度切分的精确度稍高。另外一种最少切分的方法是使每一句中切出的词数最小。

    逆向最大长度匹配法完整代码示例:

    import java.util.ArrayList;
    import java.util.List;
    
    public class jqrw006 extends TernarySearchTrie {
            
        /**
         * 匹配英文
         * 
         * @param sen
         * @param offset
         * @return
         */
        private String matchEnglish(char[] sen, int offset) {
            int i = offset;
            for (; i >= 0;) {
                char ch = sen[i];
                if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch == '\'')
                    i--;
                else
                    break;
            }
            String eng = subCharArray(sen, i + 1, offset + 1);
            return eng;
    
        }
    
        /**
         * 匹配数字
         * 
         * @param sen
         * @param offset
         * @return
         */
        private String matchNum(char[] sen, int offset) {
            int i = offset;
            for (; i >= 0;) {
                char ch = sen[i];
                if (ch >= '0' && ch <= '9')
                    i--;
                else
                    break;
            }
            String num = subCharArray(sen, i + 1, offset + 1);
            return num;
        }
    
        /**
         * 截取子串
         * 
         * @param sen
         * @param start
         * @param end
         * @return
         */
        private String subCharArray(char[] sen, int start, int end) {
            char[] chs = new char[end - start];
            if (start != end) {
                System.arraycopy(sen, start, chs, 0, end - start);
            }
            return String.valueOf(chs);
        }
        
        
        
        /**
         * 逆向最大长度匹配
         * 
         * @param sentence
         * @param offset
         * @return
         */
        private String matchLongBackward(char[] sentence, int offset) {
            String ret = null;
            if (rootNode == null || sentence == null || sentence.length == 0) {
                return ret;
            }
    
            String eng = matchEnglish(sentence, offset);
            if (!"".equals(eng)) {
                return eng;
            }
    
            String num = matchNum(sentence, offset);
            if (!"".equals(num)) {
                return num;
            }
    
            int charIndex = offset;
            TSTNode currentNode = rootNode;
            while (true) {
                if (currentNode == null) {
                    if (ret == null) {
                        String singleCn = subCharArray(sentence, offset, offset + 1);
                        return singleCn;
                    }
                    return ret;
                }
                int charComp = sentence[charIndex] - currentNode.splitchar;
                if (charComp == 0) {
                    charIndex--;
                    if (currentNode.data != null) {
                        ret = currentNode.data;
                    }
                    if (charIndex < 0) {
                        if (ret == null) {
                            String singleCn = subCharArray(sentence, offset,
                                    offset + 1);
                            return singleCn;
                        }
                        return ret;
                    }
                    currentNode = currentNode.eqNode;
                } else if (charComp < 0) {
                    currentNode = currentNode.loNode;
                } else {
                    currentNode = currentNode.hiNode;
                }
            }
        }
        
        
        /**
         * 切分
         * 
         * @param sentence
         * @return
         */
        public List<String> tag(String sentence) {
            ArrayList<String> list = new ArrayList<String>();
            char[] sen = sentence.toCharArray();
            int offset = sentence.length() - 1;
            while (offset >= 0) {
                String word = matchLongBackward(sen, offset);
                if (word == null) {
                    offset--;
                } else {
                    offset -= word.length();
                }
                if (word != null) {// 过滤掉空白字符
                    list.add(word);
                }
            }
            return list;
        }
        
    
        public static void main(String[] args) {
            jqrw006 tree=new jqrw006();
            tree.addWord("心中").data="中心";
            tree.addWord("动活").data="活动";
            tree.addWord("生学大").data="大学生";
            tree.addWord("学大").data="大学";
            
            List<String> words=tree.tag("大学生123活动abc中心");
            for (String string : words) {
                System.out.println(string);
            }
        }
    
    }
    

    所得结果为:
    在这里插入图片描述

    3.处理未登录字符串

    英文和数字要连在一起,不管它们是否在词典中。另外,对于像[ATM机]这样英文和汉字混合的词也要合并在一起。

    为了把一些连续的数字和英文切分到一起,需要区分全数字组成的词和全英文组成的词。如果匹配上了全数字组成的词,则继续往后看还有没有更多的数字。如果匹配上了全英文组成的词,则继续往后看还有没有更多的字母。

    public enum WordType {
    	English, //全英文组成的词
    	Number, //全数字组成的词
    	normal //普通的词
    }
    

    假设任何单个数字和单个字母都在词典中存在。正常匹配以后的处理:

    public String matchLong(String key,int offset){
    	Word word = matchWord(key, offset);//尝试匹配词典中的词
    	if(word == null){ //没有匹配上
    		int newOffset = matchEnglish(key, offset); //继续尝试匹配英文串
    		if(newOffset>offset)
    			return key.substring(offset,newOffset);
    		newOffset = matchNumber(key, offset); //继续尝试匹配数字串
    		if(newOffset>offset)
    			return key.substring(offset,newOffset); //返回匹配结果
    		return null;
    	}
    	if(word.type == WordType.English){
    		int oldOffset = offset+word.term.length();
    		int newOffset = matchEnglish(key, oldOffset); //继续尝试匹配英文串
    		if(newOffset>oldOffset)
    			return key.substring(offset,newOffset); //返回匹配结果
    	} else if(word.type == WordType.Number){
    		int oldOffset = offset+word.term.length();
    		int newOffset = matchNumber(key, oldOffset); //继续尝试匹配数字串
    		if(newOffset>oldOffset)
    			return key.substring(offset,newOffset); //返回匹配结果
    	}
    	return word.term;
    }
    

    把词典中所有的单词都分类:

    while ((line = in.readLine()) != null) {
    	StringTokenizer st = new StringTokenizer(line,"\t");
    	String key = st.nextToken();
    	WordType type = WordType.normal;
    	if(isAllNumber(key)) //判断是否全数字组成的词
    		type = WordType.Number;
    	else if(isAllEnglish(key)) //判断是否全英文字母组成的词
    		type = WordType.English;
    	TSTNode currentNode=creatTSTNode(key);
    	currentNode.data = new Word(key,type); //设置词本身和词的类型
    }
    

    ​ 有些词是中英文数字的,例如:bb霜、3室、乐phone、touch4、mp3、T恤。以“我买了bb霜”为例。切分出来“bb霜”,因为这是一个普通词,所以本次匹配结束。

    ​ 例如,“G2000”是个品牌,不能被分成两个词“G”和“2000”。加一个LetterOrNum。用英文字符和数字都包括的类型来处理。

    展开全文
  • 对于切词确实是一个复杂的功能,足以写上好几篇论文,...当然这种切词是对于自然语言的,对于一些有规律的字符串,请自行利用indexOf、substring、split的各类Java自带函数,没有使用额外java包的必要。 首先假如有如
  • 一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树,AC...
  • 业务场景是客户在业务办理时候需要提交一个材料列表,材料会入材料库,下次客户再来办理业务时候输入客户的身份证,会通过材料库...1.以下是两个词进行处理的核心算法 package com.ikanalyzer; import java...
  • // 文本进行分词:读入文本,输出文本,是否标注词性(0为不标注,1为标注) public boolean NLPIR_FileProcess(String txt_input, String txt_output, int i); // 添加用户词汇 public int NLPIR_AddUserWord...
  • 究其原因是ElasticSearch的标准分词器导致的,当我们创建索引时,字段使用的是标准分词器:例如 "我是程序员" 进行分词标准分词器分词效果测试:POST http://127.0.0.1:9200/blog/_analyze请求体:{ "...
  • 从文件或标准输入读取数据的一般解决之道就是读入一行文本,进行分词,然后使用Integer、Double等类的各种解析方法来解析数据:public class SimpleRead { public static BufferedReader input = new ...
  • 其中,基于字符串匹配的分词方法是把中文句子按照一定的策略将待分析的汉字串与已知且足够大的中文词典库进行比对,从而达到分词效果。而我们通常使用最多的分词策略,大致有三类,正向最大匹配法,逆向最大匹配法和...
  • 二、问题在做一个需求的时候,需要按照电话号码查询用户关系,所以我这边先讲相关信息同步到es,但是电话号码是加密的,所以显示的字符串是杂乱的,既有字母,又有斜杠等号等字符,在进行分词查询的时候匹配不到相应...
  • 其中,基于字符串匹配的分词方法是把中文句子按照一定的策略将待分析的汉字串与已知且足够大的中文词典库进行比对,从而达到分词效果。而我们通常使用最多的分词策略,大致有三类,正向最大匹配法,逆向最大匹配法和...
  • 一、问题 在做一个需求的时候,需要按照电话号码查询用户关系,所以我这边先讲相关信息同步到es,但是电话号码是加密的,所以显示的字符串是杂乱的,既有字母,又有斜杠等号等字符,在进行分词查询的时候匹配不到...
  • 对于切词确实是一个复杂的功能,足以写上好几篇论文,但是...当然这种切词是对于自然语言的,对于一些有规律的字符串,请自行利用indexOf、substring、split的各类Java自带函数,没有使用额外java包的必要。 首先
  • 对于分词系统的实现来说,主要应...其具有如下三个性质:1)根节点不包含字符(或汉字),除根节点以外的每个节点只能包含一个字符(汉字)2)从根节点到任一节点的路径上的所有节点中的字符(汉字)按顺序排列的字符串(词组...
  • 对于分词系统的实现来说,主要应...其具有如下三个性质:1)根节点不包含字符(或汉字),除根节点以外的每个节点只能包含一个字符(汉字)2)从根节点到任一节点的路径上的所有节点中的字符(汉字)按顺序排列的字符串(词组...
  • 考虑到jieba分词能够补充词表,性能相对较好,...然后利用luncene自带的 空格分词拼接的字符串进行分词,实现依靠jieba分词中文的效果 JAVA代码如下 package com.bm25; import org.apache.lucene.analysis...
  • 一、问题 在做一个需求的时候,需要按照电话号码查询用户关系,所以我这边先讲相关信息同步到es,但是电话号码是加密的,所以显示的字符串是杂乱的,既有字母,又有斜杠等号等字符,在进行分词查询的时候匹配不到...
  • 本地文件进行分词,主要是通过加载本地文件,将txt文本里的以字符串形式导入,然后进行分词处理。 package org.algorithm;import java.io.BufferedReader; import java.io.File; import java.io.FileReader; ...
  • Java 处理英文文本标点符号去除

    千次阅读 2018-11-09 08:20:56
    文章目录介绍java判断是否为标点符号 介绍 在英文文本处理时,需要将噪音字符出去,其中标点符号便属于噪音字符。...其分词结果,标点符号也成了独立的字符串,剩下的工作便是对分词后获得的字符串集合进行逐个...
  • 体现在能够根据查询的字段类型不用, 采用不同的查询方式查询的是日期或者是数组, 会把你基于字符串查询内容转为日期或数值对待查询内容是keyword类型, 则match查询不会你指定的查询进行分词.查询的内容是text类型,...

空空如也

空空如也

1 2 3 4
收藏数 63
精华内容 25
关键字:

java对字符串进行分词

java 订阅