基于向量距离的词序相似度算法

Word Order Similarity Algorithm Based on Vector Distance

手机POI搜索已经成为手机搜索的主要应用之一。该文结合手机搜索的特点以及POI数据的结构性特征采用简拼进行POI搜索。由于词序相似度是影响简拼搜索排序结果的主要因素,该文提出了基于向量距离计算词序相似度的算法。该算法采用空间向量模型作为简拼的表示方法,将提取的公共简拼映射为位置向量,进而利用位置向量间的距离计算词序相似度。通过理论分析,该算法相比基于逆序数的词序相似度算法,将时间复杂度由O(nlogn)降为O(n),空间复杂度由O(n)降为O(1)。实验结果表明,基于向量距离的词序相似度算法有效地保证了准确性,可以满足手机POI简拼搜索的应用需求,并在性能上将词序相似度的计算效率提高16.88%。

Mobile POI Search has become one of the main applications in Mobile Search. With the characters input for Mobile Search and the structural feature of POI data, Jianpin was used in the Mobile POI Search to improve the user experience. Since word order similarity is the main factor to the ranking results, an algorithm based on vector distance is devised to compute word order similarity in this paper. The algorithm first establishes the Jianpin vector space model, extracts the common part from the two Jianpin vectors and maps it into position vectors. Then it fig- ures out the similarity based on the distance between the position vectors. Theoretical analysis shows that, com- pared with the method based on reverted ordinal number, the proposed algorithm decreases the time complexity from O（nlogn） to O（n） and the space complexity from O（n） to O（1）. Experimental results confirm that the proposed algorithm can ensure the precision and improve the efficiency by 16.88%.