Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>All the answers except the one that mentions the best first algorithm are very much off. Locally sensitive hashing is basically dreaming. This is the first time I see answers so much off on stackoverflow.</p> <p>First, this is a hard, but standard problem that has been solved many years ago in different ways.</p> <p>One approach uses a trie such as the one preseted by Sedgewick here:</p> <p><a href="http://www.cs.princeton.edu/~rs/strings/" rel="noreferrer">http://www.cs.princeton.edu/~rs/strings/</a></p> <p>Sedgewick also has sample C code.</p> <p>I quote from the paper titled "Fast Algorithms for Sorting and Searching Strings" by Bentley and Sedgewick:</p> <p>"‘‘Near neighbor’’ queries <strong>locate all words within a given Hamming distance of a query word</strong> (for instance, code is distance 2 from soda). We give a new algorithm for near neighbor searching in strings, present a simple C implementation, and describe experiments on its efficiency."</p> <p>A second approach is to use indexing. Split the strings into characters n-grams and index with inverted index (google for Lucene spell checker to see how it's done). Use the index to pull potential candidates and then run hamming distance or edit distnace on the candidates. This is the approach guaranteed to work best (and relatively simple).</p> <p>A third appears in the area of speech recognition. There the query is a wav signal, and the database is a set of strings. There is a "table" that matches pieces of the signal to pieces of words. The goal is to find the best match of words to signal. This problem is known as word alignment.</p> <p>In the problem posted, there is an implicit cost of matching query parts to database parts. For example one may have different costs for deletion/insertion/substitution and even different costs for mismatching say "ph" with "f".</p> <p>The standard solution in speech recognition uses a dynamic programming approach which is made efficient via heuristics that direct pruning. In this way, only the best, say 50 candidates are kept. Thus, the name best-first search. In theory, you may not get the best match, but usually one gets a good match. </p> <p>Here is a reference to the latter approach:</p> <p><a href="http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf" rel="noreferrer">http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf</a></p> <p>Fast Approximate String Matching with Suffix Arrays and A* Parsing.</p> <p>This approach applies not only to words but to sentences.</p>
    singulars
    1. This table or related slice is empty.
    1. POFastest way to find most similar string to an input?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USStefan Savev
    1. USStefan Savev
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload