Research And Application Of Information Matching Based On Approximate String Theory

With the rapid growth of business and increased competition between telecom groups, how to improve the quality of service and reduce the cost of operation are the keys to the development of telecom industry. However, the information island problem caused by early managements and plans of foundational constructions, has made the management layer feel difficult to manage and optimize its resources. How to manage the larger and larger equipment resource information efficiently has become a kernel problem for business and service developments.Based on approximate string matching(ASM) theories, the thesis mainly talks about the ways to clean data and associate information in the Communication Network Dynamic Resource Information Synchronization and Optimization System(CNDRISOS). Firstly, the thesis introduces background knowledge used in the project and analyzes the development of approximate string matching algorithms including their design ideas at each stage. Considering the mainstream approximate string matching algorithms with high efficiency nowadays always combine bit parallelism and filter mechanism, the thesis chooses BPM-BM algorithm to present the most efficient methods currently. By analyzing its design philosophy and optimizing its filter stage, an optimized BPM-BM is proposed, and experiments have proved that the optimized algorithm could get higher matching efficiency than BPM-BM in the terms of time cost and time-cost growth in non large character set environment. With the analysis of telecom resource data features, the thesis proposes the perception of Ultimate Edit Distance(uEd), basing on the minimum edit distance of finding a similar substring, to balance the similarity between two strings. Besides, an off-line fast matching method between two string sets is proposed based on Trie Tree index and bit-parallel methods. Finally, a detailed description of Communication Network Dynamic Resource Information Synchronization and Optimization System, including its system requirements, design and development is presented. The matching algorithm based on Trie tree index and OBPM-BM is applied in particular modules in the system to clean and associate Transmission Network data. And it has helped greatly to reduce manual works and enhance work efficiency.