Cấu trúc dữ liệu đằng sau loại T9 của từ điển

Question

Từ điển T9 hoạt động như thế nào? Cấu trúc dữ liệu đằng sau nó là gì. Nếu chúng ta gõ '4663', chúng ta có được 'tốt' khi chúng ta nhấn nút, chúng ta sẽ 'biến mất' rồi 'nhà', vv ...

EDIT: Nếu người dùng gõ 46 thì nó sẽ hiển thị 'đi' và khi nào mũi tên nhấn xuống sẽ hiển thị 'đã biến mất' ...

Answer 1

Có thể thực hiện theo một số cách, một trong số đó là Trie. Các tuyến đường được đại diện bởi các chữ số và các điểm nút để thu thập các từ.

Có thể thực hiện bằng cách sử dụng bảng băm lồng nhau, khóa của hash table là chữ cái và trên mọi chữ số thuật toán tính toán tất cả các tuyến đường có thể (O (3^n) tuyến đường).

Answer 2

dịch để

{G, H, I} {M, N, O} {M, N, O} {D, E, F}

T9 hoạt động bằng cách lọc các khả năng theo tuần tự bắt đầu bằng các chữ cái đầu tiên có thể. Vì vậy, bước đầu tiên trong ví dụ của bạn là lọc danh sách từ điển thành tất cả các từ bắt đầu bằng G, H hoặc I. Bước tiếp theo, lấy danh sách đó và lọc các chữ cái thứ hai bằng M, N, O. Và cứ thế ...

Answer 3

Tôi nghĩ rằng T9 đang sử dụng Trie bit dựa trên bản đồ. Trên cấp độ đầu tiên có một 32-bit (tôi giả sử họ mở rộng đến 32) từ nơi mỗi bit đại diện cho một lá thư. Tất cả các chữ cái có giá trị như chữ cái bắt đầu cho một từ có bit được đặt.

Ở cấp độ tiếp theo, có một bản đồ 32 bit cho mỗi bit được đặt ở cấp độ trước đó. Trong các bản đồ này, mỗi bit được đặt nếu chữ cái tương ứng hợp lệ dưới dạng chữ cái thứ hai trong một từ, với chữ cái bắt đầu được quyết định bởi cấp thứ nhất.

Cấu trúc sau đó tiếp tục. Sử dụng một bit cho mỗi chữ cái làm cho một bộ nhớ rất hiệu quả. Đề án giải quyết tuy nhiên phải là thử thách. Cũng có thể có một số loại tối ưu hóa bằng cách sử dụng lược đồ trên cho các từ ngắn trong khi sử dụng một cái gì đó khác cho các từ dài hơn.

Answer 4

Tôi có thể làm điều đó bằng cách bắt đầu với một từ điển, sau đó (cho mỗi từ) đẩy từ đó vào danh sách được khóa bằng các số có thể tạo thành từ. Sau đó, có thể bạn sẽ cần sắp xếp các danh sách kết quả theo kiểu thời trang, vì vậy nhiều khả năng từ xuất hiện trước các từ ít khả năng hơn (nếu bạn có không gian, tôi cũng sẽ bao gồm một vùng nhỏ cho bộ đếm, vì vậy chúng tôi có thể tái sắp xếp các OR này chỉ đơn giản là mov ethe được sử dụng lần cuối vào trước danh sách đề xuất, vì vậy chúng tôi, theo thời gian, có xu hướng hướng tới người dùng câu trả lời tốt hơn).

Bằng cách đó, khi bạn có 4663 làm đầu vào, bạn hoàn toàn có thể truy xuất danh sách được liên kết có liên quan wit ha gần O (1) tra cứu bảng băm.

Answer 5

Tôi đoán, như trước đây T9 sử dụng một trie, trong đó các liên kết được biểu thị bằng bitmap (1 bit cho mỗi chữ cái). Đây được gọi là một cấu trúc dữ liệu gọn gàng, như Steve Hanov giải thích rất độc đáo:

http://stevehanov.ca/blog/index.php?id=120

Answer 6

C# thực hiện sử dụng Trie

 public interface ICellT9 
     { 
      void Add(string a_name); 

      List<string> GetNames(string a_number); 
     } 

     public class Cell : ICellT9 
     { 
      private Dictionary<int, Cell> m_nodeHolder; 
      private List<string> m_nameList; 

      public Cell() 
      { 
       m_nameList = new List<string>(); 
       m_nodeHolder = new Dictionary<int, Cell>(); 

       for (int i = 2; i < 10; i++) 
       { 
        m_nodeHolder.Add(i, null); 
       } 
      } 

      public void Add(string a_name) 
      { 
       Add(a_name, a_name); 
      } 

      private void Add(string a_name, string a_originalName) 
      { 
       if (string.IsNullOrEmpty(a_name) && 
        (string.IsNullOrEmpty(a_originalName) == false)) 
       { 
        m_nameList.Add(a_originalName); 
       } 
       else 
       { 
        int l_firstNumber = CharToNumber(a_name[0].ToString()); 

        if (m_nodeHolder[l_firstNumber] == null) 
        { 
         m_nodeHolder[l_firstNumber] = new Cell(); 
        } 

        m_nodeHolder[l_firstNumber].Add(a_name.Remove(0, 1), a_originalName); 
       } 
      } 

      public List<string> GetNames(string a_number) 
      { 
       List<string> l_result = null; 

       if (string.IsNullOrEmpty(a_number)) 
       { 
        return l_result; 
       } 

       int l_firstNumber = a_number[0] - '0'; 

       if (a_number.Length == 1) 
       { 
        l_result = m_nodeHolder[l_firstNumber].m_nameList; 
       } 
       else if(m_nodeHolder[l_firstNumber] != null) 
       { 
        l_result = m_nodeHolder[l_firstNumber].GetNames(a_number.Remove(0, 1)); 
       } 

       return l_result; 

      } 

      private int CharToNumber(string c) 
      { 
       int l_result = 0; 

       if (c == "a" || c == "b" || c == "c") 
       { 
        l_result = 2; 
       } 
       else if (c == "d" || c == "e" || c == "f") 
       { 
        l_result = 3; 
       } 
       else if (c == "g" || c == "h" || c == "i") 
       { 
        l_result = 4; 
       } 
       else if (c == "j" || c == "k" || c == "l") 
       { 
        l_result = 5; 
       } 
       else if (c == "m" || c == "n" || c == "o") 
       { 
        l_result = 6; 
       } 
       else if (c == "p" || c == "q" || c == "r" || c == "s") 
       { 
        l_result = 7; 
       } 
       else if (c == "t" || c == "u" || c == "v") 
       { 
        l_result = 8; 
       } 
       else if (c == "w" || c == "x" || c == "y" || c == "z") 
       { 
        l_result = 9; 
       } 

       return l_result; 
      } 
     }