Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses".
How is Google able to return near-matches and not just direct matches?
What are the methods that search engines use to perform such queries so quickly?
I know about phrase search and proximity search and how they can be implemented using a positional inverted index, but this is neither a phrase search (because the terms don't have to be directly adjacent nor in order) nor proximity search (because the terms don't have to be in order nor within a fixed width of each other — nor all present)
It seems like somehow these search engines are doing a string edit distance lookup across billions of documents in fractions of a second.
How have they managed to implement this kind of searching on top of an index?