Mirror of forum.nim-lang.org

4653 :: Fuzzy matching on table keys

• lqdev (orginal) [2019-02-12T17:57:31+01:00] view original

  Hello,

  I want to perform fuzzy matching on table keys. What I mean by that, is:

  import tables
  
  type
    Fn = proc (args: varargs[string]): int
    FnSignature = tuple
      name: string
      arity: int
      argTypes: seq[string]
  
  var signatures = newTable[FnSignature, Fn]()
  
  signatures.add(("print", 1, @["any"])) do (args: varargs[string]) -> int:
    discard
  
  echo signatures[("print", 1, @["string"])] # should return the first added element, because ``any`` describes any type
  Run

  From what I know about hash tables, it's not as simple as adding an equality operator overload to FnSignature. How do I achieve what I'm talking about?

---

• mashingan (orginal) [2019-02-12T18:40:12+01:00] view original

  Add hash function and equality operator == for custom key.

  import tables, hashes
  
  type
    Fn = proc (args: varargs[string]): int
    FnSignature = tuple
      name: string
      arity: int
      argTypes: seq[string]
  
  proc hash(fns: FnSignature): Hash = fns[0].hash
  proc `==`(a, b: FnSignature): bool = a[0] == b[0]
  
  var signatures = newTable[FnSignature, Fn]()
  
  signatures.add(("print", 1, @["any"])) do (args: varargs[string]) -> int:
    discard
  
  echo signatures[("print", 1, @["string"])]("whatev")
  Run

---

• cblake (orginal) [2019-02-12T19:26:27+01:00] view original

  What mashigan wrote may well be best suited to your exact purpose. Another possibility at least worth a shout out is collections/critbits which implements an efficient keysWithPrefix. For more fuzzy still than prefix matching, you could also do some kind of efficient edit distance-based thing, but data-structures to (attempt to) optimize that are complicated. (There is std/editdistance, though).

---

• lqdev (orginal) [2019-02-13T20:17:37+01:00] view original

  Well, it sort of did. When implementing the hash method however, I realized it's not that simple, and decided to use something like this:

  import tables
  
  type
    FnSignatureTable = ref object
      signatures: TableRef[string, seq[FnSignature]]
  Run

  Then I store all signatures in the table with their names as keys, and use an index operator with a signature as the key. I then compare the inputted signature with all the others in the seq, to see if any one matches.

---