Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Chỉ mục Không chồng Chéo Ngắn gọn
Tóm tắt
Chỉ mục văn bản là một vấn đề cơ bản trong khoa học máy tính. Mục tiêu là xử lý trước một văn bản T, để khi được cho một mẫu P, chúng ta có thể tìm tất cả các vị trí bắt đầu (hay đơn giản là các trường hợp) của P trong T một cách hiệu quả. Trong một số trường hợp, các hạn chế bổ sung được đưa ra. Chúng tôi xem xét hai biến thể, đó là vấn đề chỉ mục không chồng chéo và vấn đề chỉ mục không chồng chéo trong khoảng. Với một văn bản T có n ký tự, vấn đề chỉ mục không chồng chéo được định nghĩa như sau: xử lý trước T thành một cấu trúc dữ liệu, để cho bất kỳ mẫu P nào có |P| ký tự, chúng ta có thể báo cáo một tập hợp chứa số lượng tối đa các trường hợp không chồng chéo của P trong T. Cohen và Porat (trong: Thuật toán và tính toán, hội thảo quốc tế lần thứ 20, ISAAC 2009, Honolulu, Hawaii. Tài liệu hội nghị, 2009) đã chỉ ra rằng bằng cách duy trì một chỉ mục không gian tuyến tính trong đó cây hậu tố của T được bổ sung bằng một cấu trúc dữ liệu từ V O(n), một truy vấn P có thể được trả lời trong thời gian tối ưu O(|P|+nocc), trong đó nocc là số lượng các trường hợp được báo cáo. Chúng tôi trình bày kết quả mới sau đây. Giả sử CSA (không nhất thiết là một mảng hậu tố nén) là một chỉ mục của T có thể tính toán (i) khoảng hậu tố của P trong thời gian search(P), và (ii) một giá trị mảng hậu tố hoặc mảng hậu tố nghịch đảo trong thời gian t_SA. Bằng cách sử dụng CSA một cách độc lập, chúng tôi có thể trả lời truy vấn P trong thời gian search(P)+sort(nocc)+O(nocc·t_SA). Hàm sort(k) biểu thị thời gian để sắp xếp k số trong {1,2,…,n}. Trong vấn đề chỉ mục không chồng chéo trong khoảng, cùng với mẫu P, hai số nguyên a và b, b ≥ a, được cung cấp làm đầu vào. Nhiệm vụ là báo cáo một tập hợp chứa số lượng tối đa các trường hợp không chồng chéo của P nằm trong khoảng [a, b]. Đối với bất kỳ hằng số dương nhỏ tùy ý ε, chúng tôi trình bày một chỉ mục O(n log^ε n) với thời gian truy vấn O(|P| + nocc_{a,b}), trong đó nocc_{a,b} là số lượng các trường hợp được báo cáo. Chỉ mục của chúng tôi cải thiện kết quả của Cohen và Porat [6].
Từ khóa
Tài liệu tham khảo
Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2(1), 53–86 (2004)
Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6–8, 2001, Heraklion, Crete, Greece, pp. 476–482 (2001)
Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16–18, 1993, San Diego, CA, USA, pp. 71–80 (1993)
Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762–772 (1977)
Brodal, G.S., Fagerberg, R., Greve, M., López-Ortiz, A.: Online sorted range reporting. In: Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings, pp. 173–182 (2009)
Cohen, H., Porat, E.: Range non-overlapping indexing. In: Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings, pp. 1044–1053 (2009)
Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don’t cares. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13–16, 2004, pp. 91–100 (2004)
Crochemore, M., Iliopoulos, C.S., Kubica, M., Rahman, M.S., Walen, T.: Improved algorithms for the range next value problem and applications. In: STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21–23, 2008, Proceedings, pp. 205–216 (2008)
Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19–22, 1997, pp. 137–143 (1997)
Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552–581 (2005)
Ganguly, A., Shah, R., Thankachan, S.V.: Succinct non-overlapping indexing. In: Combinatorial Pattern Matching—26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29–July 1, 2015, Proceedings, pp. 185–195 (2015)
Ganguly, A., Shah, R., Thankachan, S.V: pBWT: achieving succinct data structures for parameterized pattern matching and related problems. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 397–407. Society for Industrial and Applied Mathematics (2017)
Ganguly, A., Shah, R., Thankachan, S.V.: Structural pattern matching-succinctly. In: 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand, pp. 35:1–35:13 (2017)
Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21–23, 2000, Portland, OR, USA, pp. 397–406 (2000)
Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)
Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: On position restricted substring searching in succinct space. J. Discrete Algorithms 17, 109–114 (2012)
Hooshmand, S., Abedin, P., Külekci, M.O., Thankachan, S.V.: Non-overlapping indexing: cache obliviously. In: Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2–4, 2018 - Qingdao, China, pp. 8:1–8:9 (2018)
Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249–260 (1987)
Keller, O., Kopelowitz, T., Lewenstein, M.: Range non-overlapping indexing and successive list indexing. In: Algorithms and Data Structures, 10th International Workshop, WADS 2007, Halifax, Canada, August 15–17, 2007, Proceedings, pp. 625–636 (2007)
Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323–350 (1977)
Mäkinen, V., Navarro, G.: Position-restricted substring searching. In: LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20–24, 2006, Proceedings, pp. 703–714 (2006)
Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935–948 (1993)
Navarro, G., Mäkinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39, 1 (2007)
Nekrich, Y., Navarro, G.: Sorted range reporting. In: Algorithm Theory—SWAT 2012: 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4–6, 2012. Proceedings, pp. 271–282 (2012)
Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249–260 (1995)
Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15–17, 1973, pp. 1–11 (1973)