Cookbook

Searching for a Single Mismatch

Application

This automaton searches for occurrences of a given string, allowing any character in the string to mismatch one time. A report event is generated when the string is found.

For example, in the sample provided, the automaton searches for occurrences of the string "Hello World". A report event from node a11 will indicate the exact string was found. A report event from node b11 or node c11 will also indicate the string was found, but in these instances, there was a single mismatching character. Specifically, b11 indicates the very last character mismatched whereas c11 indicates an earlier character in the string mismatched.

Construction

AP Workbench


Single mismatch

C Code

#include <stddef.h>
#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 = NULL;
    struct ap_anml_element element = { 0 };
    ap_anml_element_ref_t a_nodes[12];
    ap_anml_element_ref_t b_nodes[12];
    ap_anml_element_ref_t c_nodes[12];

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

    // Build the nodes for the "a" set of STEs
    element.id = "a1";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "H";
    AP_AddAnmlElement(anml_net, &a_nodes[1], &element);

    element.id = "a2";
    element.symbols = "e";
    element.start = NO_START;
    AP_AddAnmlElement(anml_net, &a_nodes[2], &element);

    element.id = "a3";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &a_nodes[3], &element);

    element.id = "a4";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &a_nodes[4], &element);

    element.id = "a5";
    element.symbols = "o";
    AP_AddAnmlElement(anml_net, &a_nodes[5], &element);

    element.id = "a6";
    element.symbols = "[\x20]";
    AP_AddAnmlElement(anml_net, &a_nodes[6], &element);

    element.id = "a7";
    element.symbols = "W";
    AP_AddAnmlElement(anml_net, &a_nodes[7], &element);

    element.id = "a8";
    element.symbols = "o";
    AP_AddAnmlElement(anml_net, &a_nodes[8], &element);

    element.id = "a9";
    element.symbols = "r";
    AP_AddAnmlElement(anml_net, &a_nodes[9], &element);

    element.id = "a10";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &a_nodes[10], &element);

    element.id = "a11";
    element.symbols = "d";
    element.match = 1;
    AP_AddAnmlElement(anml_net, &a_nodes[11], &element);

    // Build the nodes for the "b" set of STEs
    element.id = "b1";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "[^H]";
    element.match = 0;
    AP_AddAnmlElement(anml_net, &b_nodes[1], &element);

    element.id = "b2";
    element.symbols = "[^e]";
    element.start = NO_START;
    AP_AddAnmlElement(anml_net, &b_nodes[2], &element);

    element.id = "b3";
    element.symbols = "[^l]";
    AP_AddAnmlElement(anml_net, &b_nodes[3], &element);

    element.id = "b4";
    element.symbols = "[^l]";
    AP_AddAnmlElement(anml_net, &b_nodes[4], &element);

    element.id = "b5";
    element.symbols = "[^o]";
    AP_AddAnmlElement(anml_net, &b_nodes[5], &element);

    element.id = "b6";
    element.symbols = "[^\x20]";
    AP_AddAnmlElement(anml_net, &b_nodes[6], &element);

    element.id = "b7";
    element.symbols = "[^W]";
    AP_AddAnmlElement(anml_net, &b_nodes[7], &element);

    element.id = "b8";
    element.symbols = "[^o]";
    AP_AddAnmlElement(anml_net, &b_nodes[8], &element);

    element.id = "b9";
    element.symbols = "[^r]";
    AP_AddAnmlElement(anml_net, &b_nodes[9], &element);

    element.id = "b10";
    element.symbols = "[^l]";
    AP_AddAnmlElement(anml_net, &b_nodes[10], &element);

    element.id = "b11";
    element.symbols = "[^d]";
    element.match = 1;
    AP_AddAnmlElement(anml_net, &b_nodes[11], &element);

    // Build the nodes for the "c" set of STEs
    element.id = "c2";
    element.symbols = "e";
    element.match = 0;
    AP_AddAnmlElement(anml_net, &c_nodes[2], &element);

    element.id = "c3";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &c_nodes[3], &element);

    element.id = "c4";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &c_nodes[4], &element);

    element.id = "c5";
    element.symbols = "o";
    AP_AddAnmlElement(anml_net, &c_nodes[5], &element);

    element.id = "c6";
    element.symbols = "[\x20]";
    AP_AddAnmlElement(anml_net, &c_nodes[6], &element);

    element.id = "c7";
    element.symbols = "W";
    AP_AddAnmlElement(anml_net, &c_nodes[7], &element);

    element.id = "c8";
    element.symbols = "o";
    AP_AddAnmlElement(anml_net, &c_nodes[8], &element);

    element.id = "c9";
    element.symbols = "r";
    AP_AddAnmlElement(anml_net, &c_nodes[9], &element);

    element.id = "c10";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &c_nodes[10], &element);

    element.id = "c11";
    element.symbols = "d";
    element.match = 1;
    AP_AddAnmlElement(anml_net, &c_nodes[11], &element);

    // Connect the STEs together
    int i;
    for (i = 2; i < 12; ++i) {
        AP_AddAnmlEdge(anml_net, a_nodes[i - 1], a_nodes[i], 0);
        AP_AddAnmlEdge(anml_net, a_nodes[i - 1], b_nodes[i], 0);
        AP_AddAnmlEdge(anml_net, b_nodes[i - 1], c_nodes[i], 0);

        if (i > 2) {
            AP_AddAnmlEdge(anml_net, c_nodes[i - 1], c_nodes[i], 0);
        }
    }

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

    // Clean up 
    AP_DestroyAnml(anml);
    return 0;
}

Python Code

from micronap.sdk import *

A = Anml() # Create an ANML construct
AN = A.CreateAutomataNetwork() # and now create an ANML network

# These lists will hold the STEs for the design
a_nodes = [None]*12
b_nodes = [None]*12
c_nodes = [None]*12

# The list indices intentionally mimic the ID values given to each STE
# This is just for convenience
# Create the 11 nodes for the 'a' chain of STEs
a_nodes[1]  = AN.AddSTE("H", AnmlDefs.ALL_INPUT, anmlId="a1")
a_nodes[2]  = AN.AddSTE("e", anmlId="a2")
a_nodes[3]  = AN.AddSTE("l", anmlId="a3")
a_nodes[4]  = AN.AddSTE("l", anmlId="a4")
a_nodes[5]  = AN.AddSTE("o", anmlId="a5")
a_nodes[6]  = AN.AddSTE("[\x20]", anmlId="a6")
a_nodes[7]  = AN.AddSTE("W", anmlId="a7")
a_nodes[8]  = AN.AddSTE("o", anmlId="a8")
a_nodes[9]  = AN.AddSTE("r", anmlId="a9")
a_nodes[10] = AN.AddSTE("l", anmlId="a10")
a_nodes[11] = AN.AddSTE("d", anmlId="a11", match=True)

# Create the 11 nodes for the 'b' set of STEs
b_nodes[1]  = AN.AddSTE("[^H]", AnmlDefs.ALL_INPUT, anmlId="b1")
b_nodes[2]  = AN.AddSTE("[^e]", anmlId="b2")
b_nodes[3]  = AN.AddSTE("[^l]", anmlId="b3")
b_nodes[4]  = AN.AddSTE("[^l]", anmlId="b4")
b_nodes[5]  = AN.AddSTE("[^o]", anmlId="b5")
b_nodes[6]  = AN.AddSTE("[^\x20]", anmlId="b6")
b_nodes[7]  = AN.AddSTE("[^W]", anmlId="b7")
b_nodes[8]  = AN.AddSTE("[^o]", anmlId="b8")
b_nodes[9]  = AN.AddSTE("[^r]", anmlId="b9")
b_nodes[10] = AN.AddSTE("[^l]", anmlId="b10")
b_nodes[11] = AN.AddSTE("[^d]", anmlId="b11", match=True)

# Create the 10 nodes for the 'c' chain of STEs
c_nodes[2]  = AN.AddSTE("e", anmlId="c2")
c_nodes[3]  = AN.AddSTE("l", anmlId="c3")
c_nodes[4]  = AN.AddSTE("l", anmlId="c4")
c_nodes[5]  = AN.AddSTE("o", anmlId="c5")
c_nodes[6]  = AN.AddSTE("[\x20]", anmlId="c6")
c_nodes[7]  = AN.AddSTE("W", anmlId="c7")
c_nodes[8]  = AN.AddSTE("o", anmlId="c8")
c_nodes[9]  = AN.AddSTE("r", anmlId="c9")
c_nodes[10] = AN.AddSTE("l", anmlId="c10")
c_nodes[11] = AN.AddSTE("d", anmlId="c11", match=True)

# Create activation connections that connect all the STEs together
for index in [2,3,4,5,6,7,8,9,10,11]:
    AN.AddAnmlEdge(a_nodes[index-1], a_nodes[index], 0)
    AN.AddAnmlEdge(a_nodes[index-1], b_nodes[index], 0)
    AN.AddAnmlEdge(b_nodes[index-1], c_nodes[index], 0)
    if index > 2:
        AN.AddAnmlEdge(c_nodes[index-1], c_nodes[index], 0)

# Export an ANML file that can be compiled or be imported into the workbench
AN.ExportAnml('hello_world.anml')

Operation

In this automaton, nodes a1 and b1 are always active because their start conditions are set to all input, and each node continuously looks for a potential beginning to the target string "Hello World". Node a1 feeds a horizontal chain of STEs that will match, in sequence, each of the characters in the target string. If this set of nodes is traversed, node a11 will generate a report event indicating that a perfect match has been found.

If at any point in the sequence a non-matching character is encountered, a node in the b chain will match. All nodes in the b chain are set to match on the complement of the corresponding node in the a chain.

After a node in the b chain has matched, the automaton has used up the single mismatch allowed by the design. Thus, control traverses down to the c nodes, and each node in this chain must match exactly in order for the automaton to generate a report. If a second character mismatches, the chain will die out. However, if all subsequent characters after the first mismatch are satisfied, node c11 will generate a report event indicating the target string has been found with a single mismatch.

Node b11 handles the condition where the last character in the target string is the mismatching character.

Node b1 handles the condition that the first character in the target string is the mismatching character.