Automatic text classification using BPLion-neural network and semantic word processing

Text mining has become a major research topic in which text classification is the important task for finding the relevant information from the new document. Accordingly, this paper presents a semantic word processing technique for text categorization that utilizes semantic keywords, instead of using independent features of the keywords in the documents. Hence, the dimensionality of the search space can be reduced. Here, the Back Propagation Lion algorithm (BP Lion algorithm) is also proposed to overcome the problem in updating the neuron weight. The proposed text classification methodology is experimented over two data sets, namely, 20 Newsgroup and Reuter. The performance of the proposed BPLion is analysed, in terms of sensitivity, specificity, and accuracy, and compared with the performance of the existing works. The result shows that the proposed BPLion algorithm and semantic processing methodology classifies the documents with less training time and more classification accuracy of 90.9%.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

基于词汇相似度的IPC与CLC映射

专利作为一种具有特殊性质的文献,包含先进的技术方案,但存在管理困难、相对孤立、使用率低等弊端。针对该问题,定义分类法类目的概念模型,通过计算类目之间的概念相似度,为国际专利分类法与中国图书分类法建立类目映射。在计算类目相似度中引入与类目相关的词汇语义相似度计算,综合考虑类目的上下文环境对类目间关系的影响,降低专利数据的孤立性,实现专利数据与其他期刊数据的交互操作。实验表明,该方法能有效提高类目间相似度计算的准确率。     

基于倒排索引的密文数据库检索方法研究

针对实际密文数据库的应用,在全文检索倒排索引技术的基础上,设计了一种通过密文倒排索引文件对其进行快速检索的方法。密文索引文件中主要包含有索引项、相对应的记录主键等信息。检索时,通过用检索词匹配索引文件中的索引项,找到对应的记录主键集合,再根据记录主键集合查询密文数据库,获取相应的密文数据,进行解密即可获取明文数据信息。整个检索过程中不对数据库进行解密,从而实现了在不解密的情况下对密文数据库的快速检索。     

面向Kad网络的eMule文件下载控制方法

结合关键词污染和Kad索引污染技术,设计一种面向Kad网络的eMule文件下载控制方法。从Web服务器获取eMule文件的 ED2K链接,解析链接得到文件属性信息,通过构造虚假文件属性信息污染Kad网络的关键词字典和文件索引字典,从而控制eMule文件在Kad网络中的传播。实验结果表明,该方法可以延缓eMule节点之间的连接时间,达到eMule文件下载控制的目的。     

基于购物网站用户搜索日志的商品词发现

商品词是电子商务领域描述商品的新词。主要介绍基于购物网站用户搜索日志的商品词发现的方法。该方法从搜索日志中提取用户查询,对查询进行分词,采用N元递增分步算法和串频统计,计算候选串的条件概率,选择候选商品词。为了降低人工审核的成本,只对产出商品词的准确率进行评价。利用该方法在手机、面霜和香水三类商品的搜索日志上进行了实验,最高准确率达到92.58%。     

Avoiding large squares in partial words

Well-known results on the avoidance of large squares in (full) words include the following: (1) Fraenkel and Simpson showed that we can construct an infinite binary word containing at most three distinct squares; (2) Entringer, Jackson and Schatz showed that there exists an infinite binary word avoiding all squares of the form xx such that |x|≥3, and that the bound 3 is optimal; (3) Dekking showed that there exists an infinite cube-free binary word that avoids all squares xx with |x|≥4, and that the bound of 4 is best possible. In this paper, we investigate these avoidance results in the context of partial words, or sequences that may have some undefined symbols called holes. Here, a square has the form uv with u and v compatible, and consequently, such a square is compatible with a number of full words that are squares over the given alphabet. We show that (1) holds for partial words with at most two holes. We prove that (2) extends to partial words having infinitely many holes. Regarding (3), we show that there exist binary partial words with infinitely many holes that avoid cubes and have only eleven full word squares compatible with factors of it. Moreover, this number is optimal, and all such squares xx satisfy |x|≤4.     

Synchronizing automata with finitely many minimal synchronizing words

A synchronizing word for a given synchronizing DFA is called minimal if none of its proper factors is synchronizing. We characterize the class of synchronizing automata having only finitely many minimal synchronizing words (the class of such automata is denoted by FG). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n-5. We also prove that checking whether a given DFA A is in FG is co-NP-hard and provide an algorithm for this problem which is exponential in the number of states A.     

Operational state complexity of nested word automata

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The results for union and complementation differ from corresponding bounds for ordinary finite automata. For reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.