undefined | Better HN

0 pointsjustin669y ago0 comments

> Yes, but the downside is that (afaik) you can't use an index to quickly retrieve the matches in order. You really have to scan your complete dataset on every search.

I'm not sure I see what you're driving at there. If you had a finite set of strings that you might have to compare, you could (for example) populate a graph or something with weighted edges representing the Levenshtein distance between strings (vertices). Offhand, it seems like your search could basically use a hash table to find the position of the vertex representing your string on an already-populated adjacency list.

It'd be big, but in reality you'd probably only populate the edges with especially high or low weights, depending on the application?

0 comments

amelius9y ago

But how would you perform the lookup in the hash table when the string you're searching for is not (exactly) in the hash table?

justin66OP9y ago

Searching a new string - adding a string to the set - would require comparing against all items in the set, yes. That's a much less daunting prospect than what you said: You really have to scan your complete dataset on every search.

Building the index, or adding to it, is not fast (without some heuristics applied) but searching using the index isn't bad.

amelius9y ago

Okay, now I understand what you meant.

But what if a search needs to be fast regardless of whether the string has been searched for before?

1 more reply

j / k navigate · click thread line to collapse

0 pointsjustin669y ago0 comments

> Yes, but the downside is that (afaik) you can't use an index to quickly retrieve the matches in order. You really have to scan your complete dataset on every search.

It'd be big, but in reality you'd probably only populate the edges with especially high or low weights, depending on the application?

0 comments

amelius9y ago

But how would you perform the lookup in the hash table when the string you're searching for is not (exactly) in the hash table?

justin66OP9y ago

Building the index, or adding to it, is not fast (without some heuristics applied) but searching using the index isn't bad.

amelius9y ago

Okay, now I understand what you meant.

But what if a search needs to be fast regardless of whether the string has been searched for before?

1 more reply

j / k navigate · click thread line to collapse