Page 1 of 2
Map partial key match method
Posted: Mon May 18, 2020 1:26 pm
by ljgww
Consider this code
Code: Select all
NewMap txt.s()
AddMapElement(txt(),"abcd")
txt()="abcd"
AddMapElement(txt(),"bcde")
txt()="bcde"
AddMapElement(txt(),"cdef")
txt()="cdef"
; finding exact key
If FindMapElement(txt(),"cdef")
Debug "cdef found"
Debug MapKey(txt())
Else
Debug "cdef not found"
Debug MapKey(txt())
EndIf
; finding partial key
If FindMapElement(txt(),"bc")
Debug "BCDE found"
Debug MapKey(txt())
Else
Debug "BCDE not found"
Debug MapKey(txt())
EndIf
; finding exact key
If FindMapElement(txt(),"abcd")
Debug "abcd found"
Debug MapKey(txt())
Else
Debug "abcd not found"
Debug MapKey(txt())
EndIf
output
Code: Select all
cdef found
cdef
BCDE not found
cdef
abcd found
abcd
The target here is to provide partial key and find closest element in the map where key partially matches.
Is there any technique that allows finding closest map element by providing incomplete/partial key?
meaning, any faster technique apart from sequentially searching thru the list of map keys
As example shows, only exact key matches are taken in account and current element pointer shows last successful find (by exact key match).
Re: Map partial key match method
Posted: Mon May 18, 2020 1:42 pm
by NicTheQuick
A normal hash based map like Purebasic uses it can not do this.
You have to implement an algorithm that can do this or have to use external librarys that are doing this for you. Maybe also a memory based SQLite approach could help you but this seems a bit overkill to me and I am also not familiar with SQLite and if the LIKE command works with it.
Wildcard searching can potentially give you more than one result. So 'FindMapElement()' would select more than one element which is stricly spoken not really possible.
I only know about
Suffix trees and the
Knuth-Morris-Pratt algorithm but I am not sure if this can be adopted to a list of strings.
Re: Map partial key match method
Posted: Mon May 18, 2020 2:14 pm
by ljgww
Ty NickTheQuick for prompt answer.
After I posted a question I asked myself is this thing really available in some other languages like Python, JavaScript or C# who have "dictionary" like structures. And it seems to me that this is somewhat of gray area in other languages too. So far of a few languages I queried only Perl has regex on hash key, the rest like PureBasic will need an function (algorithm) to do this.
The gray area extends not that one can match more than one element (current PB Map system allows one reference to a element - current element so it is understandable that we cannot return multiple results) it actually asks for a way how to define key matching.
For example: are one is searching for a key from the left side or from the middle of the key, or some other 'like' mechanism or as in Perl provide a regex as matching method.
Hence this is not trivial task to achieve. Thank you for brainstorming.
Re: Map partial key match method
Posted: Mon May 18, 2020 2:30 pm
by ebs
An in-memory SQLite database should work.
A query like "SELECT * FROM [TABLE] WHERE KEY LIKE 'BC%' would return all elements with keys starting with 'BC'.
Re: Map partial key match method
Posted: Mon May 18, 2020 2:41 pm
by ljgww
ebs wrote:An in-memory SQLite database should work.
A query like "SELECT * FROM [TABLE] WHERE KEY LIKE 'BC%' would return all elements with keys starting with 'BC'.
While I am pondering how not to use SQL way...
Just a question here:
LIKE 'BC%' would be I guess 'left match'. (would need to go into SqlLite and see exactly what LIKE does)
At any rate, thank you too for contributing to the possible solution.
Update: All seems to be explained here:
https://www.sqlitetutorial.net/sqlite-like/
Re: Map partial key match method
Posted: Mon May 18, 2020 2:42 pm
by Marc56us
Is there any technique that allows finding closest map element by providing incomplete/partial key?
meaning, any faster technique apart from sequentially searching thru the list of map keys
The sequential search is not necessarily very slow and
ForEach and
FindString in PB allows to browse a Map or List very quickly and simply.
Code: Select all
NewMap txt.s()
AddMapElement(txt(),"abcd") : txt()="abcd"
AddMapElement(txt(),"bcde") : txt()="bcde"
AddMapElement(txt(),"cdef") : txt()="cdef"
ForEach txt()
If FindString(txt(), "bc")
Debug "Found in '" + txt() + "'"
EndIf
Next
Re: Map partial key match method
Posted: Mon May 18, 2020 2:56 pm
by ljgww
Marc56us wrote:Is there any technique that allows finding closest map element by providing incomplete/partial key?
meaning, any faster technique apart from sequentially searching thru the list of map keys
The sequential search is not necessarily very slow and
ForEach and
FindString in PB allows to browse a Map or List very quickly and simply.
Code: Select all
NewMap txt.s()
AddMapElement(txt(),"abcd") : txt()="abcd"
AddMapElement(txt(),"bcde") : txt()="bcde"
AddMapElement(txt(),"cdef") : txt()="cdef"
ForEach txt()
If FindString(txt(), "bc")
Debug "Found in '" + txt() + "'"
EndIf
Next
He he. Yes something along this example shall be OK. This would be 'anywhere in the key match'.
I was looking for the 'left match' but nevertheless this is fine idea (also gives some surprising but logical results). It is interesting example how our thinking and computer actions may differ.
For the left match I would likely go with iteration + break out from the loop to make it O(log(n)) on average, which would be OK even for a bit larger maps (essentially I am not expecting of working with extremely large sets of data so memory iteration would be fast enough). I just need beginning of the block as I assume (which may be wrong assumption) that Map Keys are sorted.
Brings to the next question are Map keys inherently sorted?, or I need to iterate whole set (making it O(n) effectively)
Re: Map partial key match method
Posted: Mon May 18, 2020 3:00 pm
by ljgww
Brings to the next question are Map keys inherently sorted?, or I need to iterate whole set (making it O(n) effectively)
Seems that they are not. They seem to keep sequence of how they were added. Gosh.
Re: Map partial key match method
Posted: Mon May 18, 2020 3:04 pm
by Marc56us
If need left match, this is faster
Code: Select all
NewMap txt.s()
AddMapElement(txt(),"abcd") : txt()="abcd"
AddMapElement(txt(),"bcde") : txt()="bcde"
AddMapElement(txt(),"cdef") : txt()="cdef"
Search$ = "bc"
Nb_char = Len(Search$)
ForEach txt()
If Left(txt(), Nb_char) = Search$
Debug "Found in '" + txt() + "'"
EndIf
Next
As far as I know, the keys aren't sorted.
Re: Map partial key match method
Posted: Mon May 18, 2020 3:28 pm
by ljgww
Cool.
Thank you Marc56us
Re: Map partial key match method
Posted: Mon May 18, 2020 11:24 pm
by idle
you want a trie instead of a map.
viewtopic.php?f=12&t=74786
Re: Map partial key match method
Posted: Tue May 19, 2020 1:23 pm
by ljgww
Thank you for this, Idle. Programming is endless amusement and this is one of best examples. It is also a discovery path - one starts a naive journey somewhere and the on the way steps on something, which, when researched deeper opens an whole area of similar issues and sometimes it grows larger to unexplored lands.
I would need to find some time to get deeper in this subject (and learn more). (Geo)Spatial trees is an area I know nothing about. At a glance - It's not likely solution for my problem (it is still a big question what is the nature of a problem I have) , but nevertheless it could be useful for someone else, who would use this thread to research alternatives to key finding means and ways. Sooner or later it turns out it is some kind of indexing problem. Then there is waging - is is worth making whole new paradigm to solve a simple problem, or problem is not simple and warrants making a library to solve it (and possibly related problems).
In fact, when I mentioned what I am looking for, a friend of mine said: I wrote my indexing system specifically to solve that problem you have encountered. So...
As it starts looking to me, there are many algorithmic approaches depending on specific need. Spatial tree is one of fine ideas. Time permitting I will check out your code too (takes a bit of a time to understand if one was blissfully ignorant like me).
Cheers!
Re: Map partial key match method
Posted: Wed May 20, 2020 7:23 am
by idle
what you've described is exactly what a prefix trie is for, otherwise you'd be looking at a DAG or something else that works.
Personally I think Tries are the the missing link, theoretically they're better than a hash table but they're hard to generalise, which is probably why you don't see them used as a standard data structure. If a Trie isn't quite what you need, perhaps you can describe the problem a bit more.
Re: Map partial key match method
Posted: Mon May 25, 2020 3:21 pm
by ljgww
idle wrote:what you've described is exactly what a prefix trie is for, otherwise you'd be looking at a DAG or something else that works.
Personally I think Tries are the the missing link, theoretically they're better than a hash table but they're hard to generalise, which is probably why you don't see them used as a standard data structure. If a Trie isn't quite what you need, perhaps you can describe the problem a bit more.
I am sure you're right (especially that I did not go deeper on this subject, hence I do not consider myself competent to argue this), but this is also balancing between using something large, complex and more efficient, or using something simple and maybe not that good but fairly OK given circumstances. It also goes to time to learn a new thing, and time one has to finish something. If whatever (occam razor) solution is not good enough given other circumstances, there is chance to improve on it later.
One thing I am trying also to understand Trie <> Tree. Is this trie a tree or it goes to trying? (English is not my first language so I may be missing something here)
Re: Map partial key match method
Posted: Mon May 25, 2020 3:25 pm
by ljgww
Note this too (a lesson after trying to find some other bug in my code):
viewtopic.php?f=12&t=75388