A method for searching a database to produce search results from queries likely to contain errors. The process begins by identifying database features likely to be useful in searching, and those features are employed to index the database. After receiving a query from a user, the system develops a rough score for the query, by extracting features from the query, assigning match scores to query features matching database features; and assigning approximation scores to query features amenable to approximation analysis with database features. The rough score is used to identify identifying a set of database records for further analysis. Those records are then subjected to a more detailed rescoring process, based on correspondence between individual query elements and individual record elements, and between the query and the database record content, taken as a whole. Based on the rescoring process, output is provided to the user.