指数模定理
doi: 10.3724/SP.J.1004.2012.01223
The Exponential Modulus Theorem
-
Abstract: Computation of exponential modula when using hashing functions such as Karp-Rabin fingerprints can be quite cumbersome especially when the alphabet size is large. In this paper, we show an interesting result which can allow this com-putation to be done in a very simple and efficient manner.
-
[1] Karp R M, Rabin M O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 1987, 31(2): 249-260[2] Chilowicz M, Duris E, Roussel G. Finding similarities in source code through factorization. Electronic Notes in Theoretical Computer Science, 2009, 238(5): 47-62[3] Aronovich L, Asher R, Bachmat E, Bitner H, Hirsch M, Klein S T. The design of a similarity based deduplication system. In: Proceedings of SYSTOR 2009: the Israeli Experimental Systems Conference. Haifa, Israel: ACM, 2009. 1-14[4] Cormode G, Muthukrishnan S. The string edit distance matching problem with moves. ACM Transactions on Algorithms, 2007, 3(1): 1-20[5] Cohen J D. Recursive hashing functions for n-grams. ACM Transactions on Information Systems, 1997, 15(3): 291-320[6] Matias Y, Rajpoot N, Sahinalp S C. The effect of flexible parsing for dynamic dictionary-based data compression. In: Proceedings of the Data Compression Conference. Snowbird, USA: IEEE, 1999. 238-246[7] Sahinalp S C, Rajpoot N M. Dictionary-based data compression: an algorithmic perspective. Lossless Compression Handbook. San Diego: Academic Press, 2003. 153-167 -
点击查看大图
计量
- 文章访问数: 1624
- HTML全文浏览量: 55
- PDF下载量: 583
- 被引次数: 0
下载:
