Cách tạo chỉ mục tiền tố đơn giản trong Java?

Question

Tôi có nhiều tập hợp url và tôi muốn triển khai tự động hoàn thành. Tôi không thích sự phức tạp của cách tiếp cận ngây thơ vì nó là tuyến tính với kích thước thiết lập:

for(String url: urls) if(url.startsWith(input) {doSomething();} 

Bây giờ tôi biết rằng trong một Hash Set, chức năng "chứa()" công trình "O (1) "nhưng không có" containsPrefix() ". Có cách nào đơn giản mà không cần sử dụng một thư viện lớn như Lucene hay tự viết mã? Tôi sẽ không có vấn đề gì nhưng nó có vẻ quá mức cần thiết cho một vấn đề đơn giản như vậy vì vậy tôi muốn biết nếu có một giải pháp đơn giản :-)

Từ các lớp khoa học máy tính của tôi Tôi nhớ một cây bao gồm các đoạn chuỗi Tôi quên nó được gọi như thế nào. Nó hoạt động như sau:

[car, care, carrot,carrotville]-> 

car 
| 
-/ 
-e 
-rrot 
    | 
    ----ville 

P .: Làm cách nào để gọi các phương thức trả về tất cả các chuỗi mà một chuỗi là tiền tố? Giống như tiền tố a là b, b là gì?

Answer 1

Nếu bạn cần phải tìm một cách hiệu quả các tiền tố của chuỗi, sử dụng một Trie, một cấu trúc dữ liệu được thiết kế một cách chính xác cho mục đích đó:

Một Trie, hoặc cây tiền tố, là một cây cấu trúc dữ liệu ra lệnh được sử dụng để lưu trữ một mảng kết hợp trong đó các khóa thường là các chuỗi. Không giống như cây tìm kiếm nhị phân, không có nút nào trong cây lưu trữ khóa được kết hợp với nút đó; thay vào đó, vị trí của nó trong cây xác định khóa mà nó được liên kết. Tất cả các hậu duệ của một node có một tiền tố chung của chuỗi kết hợp với nút đó, và gốc được kết hợp với chuỗi rỗng

Hai liên kết với sampleimplementations.

Answer 2

thời gian dài trước đây, tôi đặt một thi Trie đơn giản ở đây:

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

Tuy nhiên đây không phải là một Trie nhỏ gọn, vì vậy nó tạo ra một nút cho mỗi ký tự, tạo một nhỏ gọn là một chút phức tạp hơn.

Answer 3

Một algo thay thế tuyệt vời là một ternary search tree (thêm bộ nhớ hiệu quả) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree

đây là một Trie trong java http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 4

Các biểu thức chính quy thực hiện java.util.regex.Pattern có thể xử lý một cách hiệu quả các tiền tố:

StringBuilder buffer = new StringBuilder(); 
for (String prefix : prefixes) { 
    if (buffer.length() > 0) 
     buffer.append("|"); 
    buffer.append(prefix); 
} 
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")"); 

Bạn có thể kiểm tra tất cả các tiền tố:

boolean containsPrefix = prefixPattern.matcher(stringToTest).find(); 

Lưu ý: để đơn giản, các chuỗi tiền tố không được thoát. Regexp ký tự [,], \, *,?, $, ^, (,), {,} Và | phải được tiền tố \.