Creating a Fuzzy Match Dictionary


This automaton builds upon the previous design (Calculating Hamming Distance) to create a fuzzy match dictionary.

In this automaton, the input data stream is expected to be a set of five character words following the same format used for hamming distance. The ! symbol triggers the fuzzy matching automaton. The next five symbols are the target sequence of symbols. These five symbols will be followed by four # symbols that are used as part of the reporting process.

The quicker a report is generated, the closer the match between the input word and a word in the fuzzy matching dictionary.


AP Workbench

Fuzzy match

C Code

#include <micron/ap/ap_defs.h>
#include <micron/ap/ap_anml.h>

int main(int argc, char* argv[]) {
    ap_anml_t anml = NULL;
    ap_anml_network_t anml_net;
    struct ap_anml_element element = { 0 };
    ap_anml_element_ref_t start, cable_cnt, jelly_cnt, flaps_cnt;
    ap_anml_element_ref_t p1, p2, p3, p4, p5, p6, p7, p8, p9;
    ap_anml_element_ref_t cable_c, cable_a, cable_b, cable_l, cable_e;
    ap_anml_element_ref_t jelly_j, jelly_e, jelly_l1, jelly_l2, jelly_y;
    ap_anml_element_ref_t flaps_f, flaps_l, flaps_a, flaps_p, flaps_s;

    // Initialize the automata network
    anml = AP_CreateAnml();
    AP_CreateAutomataNetwork(anml, &anml_net, "fuzzy_match_dictionary");

    // Build the network
    element.res_type = RT_COUNTER;
    element.cnt_mode = COUNT_STOP0_PULSE; = 5;
    element.match = 1; = "cable_cnt";
    AP_AddAnmlElement(anml_net, &cable_cnt, &element); = "jelly_cnt";
    AP_AddAnmlElement(anml_net, &jelly_cnt, &element); = "flaps_cnt";
    AP_AddAnmlElement(anml_net, &flaps_cnt, &element); = "start";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "!";
    element.match = 0;
    AP_AddAnmlElement(anml_net, &start, &element);

    element.start = NO_START;
    element.symbols = "*"; = "p1";
    AP_AddAnmlElement(anml_net, &p1, &element); = "p2";
    AP_AddAnmlElement(anml_net, &p2, &element); = "p3";
    AP_AddAnmlElement(anml_net, &p3, &element); = "p4";
    AP_AddAnmlElement(anml_net, &p4, &element); = "p5";
    AP_AddAnmlElement(anml_net, &p5, &element);

    element.symbols = "#"; = "p6";
    AP_AddAnmlElement(anml_net, &p6, &element); = "p7";
    AP_AddAnmlElement(anml_net, &p7, &element); = "p8";
    AP_AddAnmlElement(anml_net, &p8, &element); = "p9";
    AP_AddAnmlElement(anml_net, &p9, &element); = "cable_c";
    element.symbols = "c";
    AP_AddAnmlElement(anml_net, &cable_c, &element); = "cable_a";
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &cable_a, &element); = "cable_b";
    element.symbols = "b";
    AP_AddAnmlElement(anml_net, &cable_b, &element); = "cable_l";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &cable_l, &element); = "cable_e";
    element.symbols = "e";
    AP_AddAnmlElement(anml_net, &cable_e, &element); = "jelly_j";
    element.symbols = "j";
    AP_AddAnmlElement(anml_net, &jelly_j, &element); = "jelly_e";
    element.symbols = "e";
    AP_AddAnmlElement(anml_net, &jelly_e, &element); = "jelly_l1";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &jelly_l1, &element); = "jelly_l2";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &jelly_l2, &element); = "jelly_y";
    element.symbols = "y";
    AP_AddAnmlElement(anml_net, &jelly_y, &element); = "flaps_f";
    element.symbols = "f";
    AP_AddAnmlElement(anml_net, &flaps_f, &element); = "flaps_l";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &flaps_l, &element); = "flaps_a";
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &flaps_a, &element); = "flaps_p";
    element.symbols = "p";
    AP_AddAnmlElement(anml_net, &flaps_p, &element); = "flaps_s";
    element.symbols = "s";
    AP_AddAnmlElement(anml_net, &flaps_s, &element);

    AP_AddAnmlEdge(anml_net, start, cable_cnt, RESET_PORT);
    AP_AddAnmlEdge(anml_net, start, jelly_cnt, RESET_PORT);
    AP_AddAnmlEdge(anml_net, start, flaps_cnt, RESET_PORT);
    AP_AddAnmlEdge(anml_net, start, p1, 0);
    AP_AddAnmlEdge(anml_net, start, cable_c, 0);
    AP_AddAnmlEdge(anml_net, start, jelly_j, 0);
    AP_AddAnmlEdge(anml_net, start, flaps_f, 0);

    AP_AddAnmlEdge(anml_net, p1, p2, 0);
    AP_AddAnmlEdge(anml_net, p2, p3, 0);
    AP_AddAnmlEdge(anml_net, p3, p4, 0);
    AP_AddAnmlEdge(anml_net, p4, p5, 0);
    AP_AddAnmlEdge(anml_net, p5, p6, 0);
    AP_AddAnmlEdge(anml_net, p6, p7, 0);
    AP_AddAnmlEdge(anml_net, p7, p8, 0);
    AP_AddAnmlEdge(anml_net, p8, p9, 0);

    AP_AddAnmlEdge(anml_net, p1, cable_a, 0);
    AP_AddAnmlEdge(anml_net, p1, jelly_e, 0);
    AP_AddAnmlEdge(anml_net, p1, flaps_l, 0);
    AP_AddAnmlEdge(anml_net, p2, cable_b, 0);
    AP_AddAnmlEdge(anml_net, p2, jelly_l1, 0);
    AP_AddAnmlEdge(anml_net, p2, flaps_a, 0);
    AP_AddAnmlEdge(anml_net, p3, cable_l, 0);
    AP_AddAnmlEdge(anml_net, p3, jelly_l2, 0);
    AP_AddAnmlEdge(anml_net, p3, flaps_p, 0);
    AP_AddAnmlEdge(anml_net, p4, cable_e, 0);
    AP_AddAnmlEdge(anml_net, p4, jelly_y, 0);
    AP_AddAnmlEdge(anml_net, p4, flaps_s, 0);

    AP_AddAnmlEdge(anml_net, cable_c, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, cable_a, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, cable_b, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, cable_l, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, cable_e, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, jelly_j, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, jelly_e, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, jelly_l1, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, jelly_l2, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, jelly_y, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, flaps_f, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, flaps_l, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, flaps_a, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, flaps_p, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, flaps_s, flaps_cnt, COUNT_ONE_PORT);

    AP_AddAnmlEdge(anml_net, p6, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p6, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p6, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p7, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p7, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p7, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p8, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p8, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p8, flaps_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p9, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p9, jelly_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p9, flaps_cnt, COUNT_ONE_PORT);

    // Export the network to an ANML file
    AP_ExportAnml(anml_net, "fuzzy_match_dictionary.anml", "");

    // Clean up 
    return 0;

Python Code

from micronap.sdk import *

def main():
    # Initialize the automata network
    A = Anml()
    AN = A.CreateAutomataNetwork(anmlId='fuzzy_match_dictionary')

    # Build the network
    start = AN.AddSTE('!', startType=AnmlDefs.ALL_INPUT, anmlId='start')
    cable_cnt = AN.AddCounter(5, mode=CounterMode.STOP_PULSE, match=True, anmlId='cable_cnt')
    jelly_cnt = AN.AddCounter(5, mode=CounterMode.STOP_PULSE, match=True, anmlId='jelly_cnt')
    flaps_cnt = AN.AddCounter(5, mode=CounterMode.STOP_PULSE, match=True, anmlId='flaps_cnt')

    p1 = AN.AddSTE('*', anmlId='p1')
    p2 = AN.AddSTE('*', anmlId='p2')
    p3 = AN.AddSTE('*', anmlId='p3')
    p4 = AN.AddSTE('*', anmlId='p4')
    p5 = AN.AddSTE('*', anmlId='p5')

    p6 = AN.AddSTE('#', anmlId='p6')
    p7 = AN.AddSTE('#', anmlId='p7')
    p8 = AN.AddSTE('#', anmlId='p8')
    p9 = AN.AddSTE('#', anmlId='p9')

    cable_c = AN.AddSTE('c', anmlId='cable_c')
    cable_a = AN.AddSTE('a', anmlId='cable_a')
    cable_b = AN.AddSTE('b', anmlId='cable_b')
    cable_l = AN.AddSTE('l', anmlId='cable_l')
    cable_e = AN.AddSTE('e', anmlId='cable_e')

    jelly_j = AN.AddSTE('j', anmlId='jelly_j')
    jelly_e = AN.AddSTE('e', anmlId='jelly_e')
    jelly_l1 = AN.AddSTE('l', anmlId='jelly_l1')
    jelly_l2 = AN.AddSTE('l', anmlId='jelly_l2')
    jelly_y = AN.AddSTE('y', anmlId='jelly_y')

    flaps_f = AN.AddSTE('f', anmlId='flaps_f')
    flaps_l = AN.AddSTE('l', anmlId='flaps_l')
    flaps_a = AN.AddSTE('a', anmlId='flaps_a')
    flaps_p = AN.AddSTE('p', anmlId='flaps_p')
    flaps_s = AN.AddSTE('s', anmlId='flaps_s')

    AN.AddAnmlEdge(start, cable_cnt, AnmlDefs.RESET_PORT)
    AN.AddAnmlEdge(start, jelly_cnt, AnmlDefs.RESET_PORT)
    AN.AddAnmlEdge(start, flaps_cnt, AnmlDefs.RESET_PORT)
    AN.AddAnmlEdge(start, p1, 0)
    AN.AddAnmlEdge(start, cable_c, 0)
    AN.AddAnmlEdge(start, jelly_j, 0)
    AN.AddAnmlEdge(start, flaps_f, 0)

    AN.AddAnmlEdge(p1, p2, 0)
    AN.AddAnmlEdge(p2, p3, 0)
    AN.AddAnmlEdge(p3, p4, 0)
    AN.AddAnmlEdge(p4, p5, 0)
    AN.AddAnmlEdge(p5, p6, 0)
    AN.AddAnmlEdge(p6, p7, 0)
    AN.AddAnmlEdge(p7, p8, 0)
    AN.AddAnmlEdge(p8, p9, 0)

    AN.AddAnmlEdge(p1, cable_a, 0)
    AN.AddAnmlEdge(p1, jelly_e, 0)
    AN.AddAnmlEdge(p1, flaps_l, 0)
    AN.AddAnmlEdge(p2, cable_b, 0)
    AN.AddAnmlEdge(p2, jelly_l1, 0)
    AN.AddAnmlEdge(p2, flaps_a, 0)
    AN.AddAnmlEdge(p3, cable_l, 0)
    AN.AddAnmlEdge(p3, jelly_l2, 0)
    AN.AddAnmlEdge(p3, flaps_p, 0)
    AN.AddAnmlEdge(p4, cable_e, 0)
    AN.AddAnmlEdge(p4, jelly_y, 0)
    AN.AddAnmlEdge(p4, flaps_s, 0)

    AN.AddAnmlEdge(cable_c, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(cable_a, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(cable_b, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(cable_l, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(cable_e, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(jelly_j, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(jelly_e, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(jelly_l1, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(jelly_l2, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(jelly_y, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(flaps_f, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(flaps_l, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(flaps_a, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(flaps_p, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(flaps_s, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)

    AN.AddAnmlEdge(p6, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p6, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p6, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p7, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p7, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p7, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p8, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p8, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p8, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p9, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p9, jelly_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p9, flaps_cnt, AnmlDefs.COUNT_ONE_PORT)

    # Export the network to an ANML file

if __name__ == '__main__':


See Appendix A: ANML Code.


This automaton contains three hamming distance chains, all of which function exactly as described in Calculating Hamming Distance.

Although only three hamming distance chains are shown, this design can be extended to incorporate possibly hundreds of hamming distance chains, each one searching for a different word likeness in the input data stream.

Report generation occurs in the same way it does in the hamming distance design. Chains that closely match the input will generate reports earlier than chains that only loosely match the input. It is possible for more than one chain to report in the same symbol cycle; this indicates that the input equally matches more than one word programmed into the automaton.

For example, the following actions would occur with the input sequence !cells####:

  1. The input symbol chain cable will report in the ninth symbol cycle, indicating a hamming distance of 3.
  2. The input symbol chain jelly will report in the eight symbol cycle, indicating a hamming distance of 2.
  3. The input symbol chain flaps will report in the tenth symbol cycle, indicating a hamming distance of 4.

Therefore, the automaton word that most closely matches cells is jelly (the one with the lowest hamming distance).

If the word !falls#### were presented to the automaton, all three words (jelly, cable, and flaps) would report in the same symbol cycle, indicating they are all equally close matches to the input.