Cấu trúc dữ liệu C# nào cho phép tìm kiếm một cặp dây có hiệu quả nhất đối với các đoạn mã?

Question

Tôi có một cấu trúc dữ liệu trong đó bao gồm các cặp giá trị, là người đầu tiên trong số đó là một số nguyên và lần thứ hai trong số đó là một chuỗi chữ và số (có thể bắt đầu với chữ số):

+--------+-----------------+ 
| Number | Name   | 
+--------+-----------------+ 
| 15  | APPLES   | 
| 16  | APPLE COMPUTER | 
| 17  | ORANGE   | 
| 21  | TWENTY-1  | 
| 291 | 156TH ELEMENT | 
+--------+-----------------+ 

Một bảng trong số này sẽ bao gồm tối đa 100.000 hàng.

Tôi muốn cung cấp chức năng tra cứu trong đó người dùng có thể tra cứu số đó (như thể đó là một chuỗi) hoặc các phần của chuỗi. Lý tưởng là tra cứu sẽ "sống" như kiểu người dùng; sau mỗi lần nhấn phím (hoặc có thể sau một khoảng thời gian trễ ngắn ~ 250-500 ms) một tìm kiếm mới sẽ được thực hiện để tìm các ứng cử viên có khả năng nhất. Vì vậy, ví dụ tìm kiếm trên

• 1 sẽ trở lại 15 APPLES, 16 APPLE COMPUTER, 17 ORANGE, và 291 156TH ELEMENT
• 15 sẽ thu hẹp tìm kiếm để 15 APPLES, 291 156TH ELEMENT
• AP sẽ trở lại 15 APPLES và 16 APPLE COMPUTER
• (lý tưởng , nhưng không bắt buộc) ELEM sẽ trả lại 291 156TH ELEMENT.

Tôi đã suy nghĩ về việc sử dụng hai Dictionary<string, string> s kể từ cuối cùng là int s đang được so sánh như string s - một di chúc chỉ mục bằng phần số nguyên và các khác do phần chuỗi.

Nhưng thực sự tìm kiếm theo chuỗi con không nên sử dụng hàm băm và có vẻ như lãng phí khi sử dụng gấp đôi bộ nhớ mà tôi cảm thấy mình cần.

Cuối cùng câu hỏi là, có cách nào hoạt động tốt để tìm kiếm văn bản hai danh sách lớn đồng thời cho các bản chất không?

Nếu không, làm thế nào về một SortedDictionary? Có thể tăng hiệu suất nhưng vẫn không giải quyết được vấn đề băm.

Nghĩ về việc tạo một regex khi đang bay, nhưng tôi nghĩ điều đó sẽ thực hiện khủng khiếp.

Tôi mới tham gia C# (có nguồn gốc từ thế giới Java) nên tôi chưa xem xét LINQ; đó có phải là câu trả lời không?

EDIT 18:21 EST: Không có chuỗi nào trong trường "Tên" sẽ dài hơn 12-15 ký tự, nếu điều đó ảnh hưởng đến giải pháp tiềm năng của bạn.

Answer 1

Tôi muốn xem xét sử dụng cấu trúc dữ liệu Trie.

Làm cách nào để đạt được điều đó? Lá sẽ đại diện cho "hàng" của bạn, nhưng bạn sẽ có "hai con đường" cho mỗi cá thể bộ nhớ của một "hàng" (một cho số và một cái khác cho tên).

Sau đó bạn có thể hy sinh tình trạng của bạn:

(ideally, but not required) ELEM will return 291 156TH ELEMENT. 

Hoặc cung cấp thậm chí nhiều đường dẫn đến trường hợp hàng của bạn.

Answer 2

Nếu có thể, tôi sẽ tránh tải tất cả 100.000 mục nhập vào bộ nhớ. Tôi sẽ sử dụng cơ sở dữ liệu hoặc Lucene.Net để lập chỉ mục các giá trị. Sau đó, sử dụng cú pháp truy vấn thích hợp để tìm kiếm kết quả một cách hiệu quả.

Answer 3

Vì bạn đang tìm kiếm từ đầu, bộ sưu tập dựa trên khóa sẽ không hoạt động, trừ khi bạn lưu trữ tất cả các từ có thể có, như "a", "ap", "app", "appl", "apple ".

Đề xuất của tôi là sử dụng System.Collections.Generic.List<T> kết hợp với tìm kiếm nhị phân. Bạn sẽ phải cung cấp cho riêng mình IComparer<T>, cũng tìm thấy sự bắt đầu của các từ. Bạn sẽ sử dụng hai cấu trúc dữ liệu.

Một List<KeyValuePair<string,int>> giữ các từ đơn lẻ hoặc số làm khóa và số làm giá trị.

One Dictionary<int,string> giữ nguyên tên.

Bạn sẽ tiến hành như thế này:

1. Tách câu của bạn (cả tên) vào những từ đơn lẻ.

2. Thêm chúng vào danh sách có từ là khóa và số làm giá trị của KeyValuePair.

3. Thêm số vào danh sách dưới dạng khóa và làm giá trị của KeyValuePair.

4. Khi danh sách đầy, hãy sắp xếp danh sách để cho phép tìm kiếm nhị phân.

Tìm kiếm một sự khởi đầu của một từ:

1. Tìm kiếm trong danh sách bằng cách sử dụng BinarySearch kết hợp với IComparer<T> của bạn.

2. Chỉ mục bạn nhận được từ tìm kiếm có thể không phải là trường hợp đầu tiên áp dụng, vì vậy hãy quay lại danh sách cho đến khi bạn tìm thấy mục nhập đầu tiên phù hợp.

3. Sử dụng số được lưu làm giá trị trong danh sách, tra cứu toàn bộ tên trong từ điển bằng cách sử dụng số này làm khóa.