1. A method of generating search trees indicating next valid characters for an input interface of a navigation device, said method comprising: retrieving information on a first set of character strings and information on a second set of character strings, said first and second sets being different from each other; determining, based on said information on said first set and said information on said second set, a search sub-tree which indicates next valid characters for both a subset of said first set of character strings and another subset of said second set of character strings; generating a first search tree based on said information on said first set and a second search tree based on said information on said second set, wherein said first search tree and said second search tree are generated such that a node of said first search tree references said search sub tree and that another node of said second search tree references said search sub-tree, and storing said first search tree and said second search tree in a data base.