百度语言翻译机
题目来源于http://www.programfan.com/acm/,题目如下:
时限 1s
百度的工程师们是非常注重效率的,在长期的开发与测试过程中,他们逐渐创造了一套
独特的缩略语。他们在平时的交谈、会议,甚至在各种技术文档中都会大量运用。
为了让新员工可以更快地适应百度的文化,更好地阅读公司的技术文档,人力资源部决
定开发一套专用的翻译系统,把相关文档中的缩略语和专有名词翻译成日常语言。
输入要求:
输入数据包含三部分:
1. 第一行包含一个整数N(N<=10000),表示总共有多少个缩略语的词条;
2. 紧接着有N行的输入,每行包含两个字符串,以空格隔开。第一个字符串为缩略语(
仅包含大写英文字符,长度不超过10字节),第二个字符串为日常语言(不包含空格,
长度不超过255字节);
3. 从第N+2开始到输入结束为包含缩略语的相关文档(总长度不超过1000000个字节)。
例:
时限 1s
百度的工程师们是非常注重效率的,在长期的开发与测试过程中,他们逐渐创造了一套
独特的缩略语。他们在平时的交谈、会议,甚至在各种技术文档中都会大量运用。
为了让新员工可以更快地适应百度的文化,更好地阅读公司的技术文档,人力资源部决
定开发一套专用的翻译系统,把相关文档中的缩略语和专有名词翻译成日常语言。
输入要求:
输入数据包含三部分:
1. 第一行包含一个整数N(N<=10000),表示总共有多少个缩略语的词条;
2. 紧接着有N行的输入,每行包含两个字符串,以空格隔开。第一个字符串为缩略语(
仅包含大写英文字符,长度不超过10字节),第二个字符串为日常语言(不包含空格,
长度不超过255字节);
3. 从第N+2开始到输入结束为包含缩略语的相关文档(总长度不超过1000000个字节)。
例:
6
PS 门户搜索部
NLP 自然语言处理
PM 产品市场部
HR 人力资源部
PMD 产品推广部
MD 市场发展部
百度的部门包括PS,PM,HR,PMD,MD等等,其中PS还包括NLP小组。
PS 门户搜索部
NLP 自然语言处理
PM 产品市场部
HR 人力资源部
PMD 产品推广部
MD 市场发展部
百度的部门包括PS,PM,HR,PMD,MD等等,其中PS还包括NLP小组。
输出要求:
输出将缩略语转换成日常语言后的文档。(将缩略语转换成日常语言,其他字符保留原
样)。例:
输出将缩略语转换成日常语言后的文档。(将缩略语转换成日常语言,其他字符保留原
样)。例:
百度的部门包括门户搜索部,产品市场部,人力资源部,产品推广部,市场发展部等等 ,其中门户搜索部还包括自然语言处理小组。
注意:
1. 输入数据中是中英文混合的,中文采用 GBK 编码。
2. 为保证答案的唯一性,缩率语的转换采用正向最大匹配(从左到右为正方向)的原则。请注意输入例子中 PMD 的翻译。
2. 为保证答案的唯一性,缩率语的转换采用正向最大匹配(从左到右为正方向)的原则。请注意输入例子中 PMD 的翻译。
实现思路:
1. 从输入的文本串读取大写字母字符串
2. 使用 正向最大匹配算法 对步骤1截取的大写字母字符串 进行翻译,翻译过程大致如下:
由题意知,缩略语长度不超过10,所以在此定义最长的匹配长度为10.
每次从左到右读取字符串的前10个字节(如果字符串长度<10,则读取整个字符串),判断该子串是否在语料库中存在,若存在,则返回对应的翻译结 果;否则,去掉子串的最后一个字节,再与语料库进行匹配。如此反复执行,直至找到对应翻译结果为止(如果读到最后一个大写字母,仍未找到翻译结果,则表明 该字母并非需要需要翻译,直接输出即可)。
正向最大匹配算法 举例来说:
每次从左到右读取字符串的前10个字节(如果字符串长度<10,则读取整个字符串),判断该子串是否在语料库中存在,若存在,则返回对应的翻译结 果;否则,去掉子串的最后一个字节,再与语料库进行匹配。如此反复执行,直至找到对应翻译结果为止(如果读到最后一个大写字母,仍未找到翻译结果,则表明 该字母并非需要需要翻译,直接输出即可)。
正向最大匹配算法 举例来说:
正向最大匹配算法 举例 写道
以 “我是一个好人” 为例
正向的顺序为
我是一
我是
我 ===> 得到一个词
是一个
是一
是 ===>得到一个词
一个好
一个===> 得到一个词
好人===>得到一个词
结果 我、是、一个、好人
正向的顺序为
我是一
我是
我 ===> 得到一个词
是一个
是一
是 ===>得到一个词
一个好
一个===> 得到一个词
好人===>得到一个词
结果 我、是、一个、好人
3.将翻译的结果拼接在 最终的翻译字符串尾部。
4.将剩余的非大写字母字符串拼接在 最终的翻译字符串尾部。
具体代码如下:
package com.sabrina.baiduTranslation; import java.util.HashMap; import java.util.Map; import java.util.regex.Matcher; import java.util.regex.Pattern; public class MaximumMatchingMethod { // 最大匹配长度 private static final int MAX_MATCHING_LENGTH = 10; // 语料库 private Map corpus = null; MaximumMatchingMethod(Map corpus) { this.corpus = corpus; } public static void main(String[] args) { // 手动设置语料库,也可以从文件中读取 final Map corpus = new HashMap(); corpus.put("PS", "门户搜索部"); corpus.put("NLP", "自然语言处理"); corpus.put("PM", "产品市场部"); corpus.put("HR", "人力资源部"); corpus.put("PMD", "产品推广部"); corpus.put("MD", "市场发展部"); // 创建 正向最大匹配算法 对象 MaximumMatchingMethod maxMatching = new MaximumMatchingMethod(corpus); // 测试文本段 String content = "百度的部门包括 PS , PM , HR , PMD , MD 等等,其中 PS 还包括 NLP 小组。"; // 大写字母字符串正则匹配 Pattern pattern = Pattern.compile("[A-Z]+"); Matcher matcher = pattern.matcher(content); StringBuffer sbr = new StringBuffer(); String subString = ""; // 循环判断是否匹配到文本段中的大写字符字符串 while(matcher.find()) { // 取出匹配到的大写字符串 subString = content.substring(matcher.start(), matcher.end()); // 使用 正向最大匹配算法 获得翻译后的结果串 matcher.appendReplacement(sbr, maxMatching.getMaximumMathcingString(subString)); } // 将剩余字符串拼接到缓存StringBuffer对象尾部 matcher.appendTail(sbr); System.out.println(sbr.toString()); // 测试getMaximumMathcingString()方法 System.out.println(); System.out.println(maxMatching.getMaximumMathcingString("PSNNLPPMHRPMDDMD")); } public String getMaximumMathcingString(String toMatchedString) { // 打印待分析的字符串 System.out.println("----------------- " + toMatchedString + " -----------------"); byte[] toMatchedBytes = toMatchedString.getBytes(); String result = ""; int startIndex = 0; int offset = MAX_MATCHING_LENGTH; while(startIndex < toMatchedBytes.length) { // 如果起始索引到字符串末尾的距离 小于 最大匹配长度,则偏移量为 // 字符串末尾 - 起始索引; // 否则,偏移量为 最大匹配长度 offset = ((startIndex + MAX_MATCHING_LENGTH) > toMatchedBytes.length) ? (toMatchedBytes.length - startIndex) : MAX_MATCHING_LENGTH; String subString = ""; // 如果偏移量>0 并且当前子串在语料库中不存在 while(offset > 0 && !corpus.containsKey((subString = toMatchedString.substring(startIndex, startIndex + offset)))) { -- offset; } if(offset > 0) { // 子串在语料库中存在 result += corpus.get(subString); startIndex = startIndex + offset; } else { result += subString; startIndex = startIndex + 1; } } return result; } }
PS: 若思路或代码中有误,敬请指正~
相关推荐
Java调用百度翻译API翻译实例,您可以在上自行修改。此实例默认支持英文翻译成中文,您可以自行修改!(有JSON工具类,可以使用工具类得到中英文内容)
java实现的翻译功能,实现多语言翻译,很不错的东西
纯java(没有使用第三方的jar包)调用百度翻译接口的简单实例.
2006年百度之星程序设计大赛初赛题目——百度语言翻译机,题目不是很难,我用了C,C++,C#三种语言实现,在VS2008环境下编译通过。相关博文地址:http://blog.csdn.net/jocodeoe/article/details/7039285
Java调用百度翻译接口,实现简单的翻译功能。
PHP对接百度翻译接口API 实现多国语言翻译
Java版百度翻译API的用法示例,在微信服务号开发翻译功能时,调用了百度的翻译API,功能已经实现,想做翻译功能的可看Demo,直接就可以用。。
调用百度翻译的接口,实现简单的多语言互译的简单Demo
简单的实现了通过语音直接说出你要翻译的中文或者英文,他会根据你说出的内容进行判断,如果是英文它默认的会给你翻译成英文,如果是英文翻译成中文,笔者在这里只做了中英文的翻译(项目需求),如果需要可以加入...
java实现的翻译功能,调用有道字典,可直接运行
java实现google翻译 可以用的!
【Java毕业设计】代毕业设计,java调用百度API实现多种语言翻译并在线朗读
本翻译机支持下列语言翻译: 中英、英中、中日、日中、中韩、韩中、中法、法中、中西、西中、中泰、泰中、中阿、阿中、中俄、俄中、英日、日英、英泰、泰英、英阿、阿英、英西、西英、英葡、葡英。 主要使用了北大唐...
google-api-translate-java(Java 语言对Google翻译引擎的封装类库).7z
java语言实现google的机器翻译模型
google-api-translate-java(Java 语言对Google翻译引擎的封装类库)
微软翻译api的java实现
java帮助文档 JDK API java 帮助文档 谷歌翻译 JDK1.8 API 中文 谷歌翻译版 java帮助文档 Java最新帮助文档 本帮助文档是使用谷歌翻译
主要为大家详细介绍了java实现英文翻译程序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
百度翻译API调用PHP实现,