编程算法 – 字典分词 代码(C)

编程算法 – 字典分词 代码(C)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

编程算法 - 字典分词 代码(C)此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

字典分词 代码(C)


本文地址: http://blog.csdn.net/caroline_wendy


给定字典, 给定一句话, 进行分词. 

使用深度遍历(DFS)的方法.

使用一个參数string, 保存当前分支的分词后的句子; 使用一个參数vector, 保存全部可能的组合.

使用一个验证函数, 推断句子能否够分词.


代码:

/*
 * main.cpp
 *
 *  Created on: 2014.9.18
 *  Author: Spike
 *  Copyright (c) 2014年 WCL. All rights reserved.
 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

bool Match(string s, string m) {
	int l = m.length();
	if (s.substr(0, l) == m) {
		return true;
	}
	return false;
}

bool Validate(string s, vector<string> &dict) {
	//1. calculate all alphabets in the query
	set<char> sc;
	for (size_t i = 0; i < s.length(); i++) {
		sc.insert(s[i]);
	}
	//2. calculate all alphabets in the dictionary
	set<char> dc;
	for (vector<string>::iterator it = dict.begin();
			it != dict.end(); it++)
	{
		for (size_t i = 0; i < (*it).length(); i++) {
			dc.insert((*it)[i]);
		}
	}
	for (set<char>::iterator it = sc.begin(); it != sc.end(); it++) {
		if (dc.find(*it) == dc.end()) {
			return false;
		}
	}
	return true;
}

string Split(string s, vector<string> &dict, string cur, vector<string>& list) {
	if (s.length() == 0) {
		list.push_back(cur);
		return s;
	}
	for (vector<string>::iterator it = dict.begin(); it != dict.end(); it++) {
		if (Match(s, *it)) {
			string tmp = cur;
			string latter = s.substr(it->length(), s.length() - it->length());
			cur += (*it) + "~"; // add current word to cur_str
			cur += Split(latter, dict, cur, list); // split remaining words
			cur = tmp; //back to last status
		}
	}
	return "No Result";
}

vector<string> SplitWords(string s, vector<string> &dict) {
	string cur = "";
	vector<string> list;
	if (!Validate(s, dict)) {
		return list;
	}
	Split(s, dict, cur, list);
	return list;
}


int main()
{
    vector<string> dict={"程序猿","公务员","员","我","喜","做","程序","一","欢","喜欢","做一个","一个"};
    vector<string> words = SplitWords("我喜欢做一个程序猿", dict);
    for (vector<string>::iterator it=words.begin(); it!=words.end(); it++) {
        cout<<(*it)<<endl;
    }
    return 0;
}

简化版本号(没有验证):

/*
 * main.cpp
 *
 *  Created on: 2014.9.18
 *  Author: Spike
 *  Copyright (c) 2014年 WCL. All rights reserved.
 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

bool Match(string s, string m) {
	int l = m.length();
	if (s.substr(0, l) == m) {
		return true;
	}
	return false;
}

string Split(string s, vector<string> &dict, string cur, vector<string>& list) {
	if (s.length() == 0) {
		list.push_back(cur);
		return s;
	}

	for (vector<string>::iterator it = dict.begin(); it != dict.end(); it++) {
		if (Match(s, *it)) {
			string tmp = cur;
			string latter = s.substr(it->length());
			cur += (*it) + " | "; // add current word to cur_str
			cur += Split(latter, dict, cur, list); // split remaining words
			cur = tmp; //back to last status
		}
	}

	return "No Result";
}

vector<string> SplitWords(string s, vector<string> &dict) {
	string cur = "";
	vector<string> list;
	Split(s, dict, cur, list);
	return list;
}


int main()
{
    vector<string> dict={"程序猿","公务员","员","我","喜","做","程序","一","欢","喜欢","做一个","一个"};
    string s = "我喜欢做一个程序猿";
    vector<string> words = SplitWords(s, dict);
    for (vector<string>::iterator it=words.begin(); it!=words.end(); it++) {
        cout<<(*it)<<endl;
    }
    return 0;
}

输出:

我~喜~欢~做~一个~程序猿~
我~喜~欢~做~一个~程序~员~
我~喜~欢~做一个~程序猿~
我~喜~欢~做一个~程序~员~
我~喜欢~做~一个~程序猿~
我~喜欢~做~一个~程序~员~
我~喜欢~做一个~程序猿~
我~喜欢~做一个~程序~员~

编程算法 - 字典分词 代码(C)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117972.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号