Filter Based Fast Matching of Long Patterns by Using SIMD Instructions.

摘要: SIMD instructions exist in many recent microprocessors supporting parallel execution of some operations on multiple data simultaneously via a set special working limited number registers. Although the usage is explored deeply multimedia processing, implementation encryption/decryption algorithms, and scientific calculations, it has not been much addressed pattern matching. This study introduces filter based exact matching algorithm for searching long strings benefiting from Intel’s SSE (streaming extensions) technology. The proposed worst, best, average time complexities O(n · m), O(n/m), O(n/m + n m/2) respectively, while an m bytes text bytes. Experiments small, medium, large alphabet files are conducted to compare performance new with other alternatives, which known be very fast string search operations. In all cases clear winner average. When compared nearest successor, speed improved orders magnitude small sequences. 40 % better medium alphabets, 50 natural language text.