Efficient graph tree based address autocomplete and autocorrection

A computer-implemented method comprising:

• as performed by a computing system including one or more computer processors configured to execute specific instructions,
• receiving at least one character in a user-input address string;
• accessing an address graph including (i) for particular address-components of a plurality of address-components of an address string, a separate graph tree for each of the particular address-components, wherein the address string is stored in an address database storing a plurality of address strings, wherein the address string is associated with a unique identifier, and wherein each address string of the plurality of address strings includes at least some of the plurality of address-components organized in a sequence, (ii) a plurality of paths, wherein each path of the plurality of paths is formed from at least two separate graph trees connected by a tree jump, wherein each path of the plurality of paths encodes a character sequence of a corresponding address string of the plurality of address strings, and (iii) for each path of the plurality of paths, an association between a terminal vertex of the path and the unique identifier of the corresponding address string;
• performing a depth-first search along a subset of the plurality of paths through the at least two separate graph trees to compute, for each path of the subset, an edit distance between the user-input address string and at least a portion of the character sequence encoded by the path;
• for each path of the subset, determining that the edit distance is less than a maximum edit distance;
• for each path of the subset, looking up the corresponding address string in the address database using the unique identifier associated with the terminal vertex of the path;
• and
• causing output of a search result set including at least a predetermined number of the corresponding address strings, for display.

A non-transitory computer-readable medium storing instructions that, when executed by one or more processors, cause the one or more processors to at least:

• receive at least one character in a user-input address string;
• access an address graph including (i) for particular address-components of a plurality of address-components of an address string, a separate graph tree for each of the particular address-components, wherein the address string is stored in an address database including a plurality of address strings, and wherein each address string of the plurality of address strings includes a least some of the plurality of address-components organized in a sequence, (ii) a plurality of paths, wherein each path of the plurality of paths is formed from at least two separate graph trees connected by a tree jump, wherein each path of the plurality of paths encodes a character sequence of a corresponding address string of the plurality of address strings, and (iii) for each path of the plurality of paths, an association between a terminal vertex of the path and a unique identifier of the corresponding address string in the address database;
• perform a search along a subset of the plurality of paths through the at least two separate graph trees to compute, for each path of the subset, an edit distance between the user-input address string and at least a portion of the character sequence encoded by the path;
• for each path of the subset, determine that the edit distance is less than a maximum edit distance;
• for each path of the subset, look up the corresponding address string in the address database using the unique identifier associated with the terminal vertex of the path;
• and
• cause output of a result set including at least a predetermined number of the corresponding address strings, for display.