Regex .matchFirst benchmark

///////////////////////////////////////////////////////////////////////////////
//                           !!! LICENSE !!!
// This example may be subject to the terms of the GPLv2, given that the
// regular expression used was taken from the US Address Parser project:
// https://usaddress.codeplex.com/
//
///////////////////////////////////////////////////////////////////////////////
//
// Originally I tried to reproduce the problem by concocting a shoddy
// datetime parser, in the hopes that it would be complex enough to demonstrate
// the problem.  It wasn't.  So the address parser that originally found this
// slowdown was used instead.  There are still peices of code that reference
// the datetime parsing.  It doesn't seem to matter, because the slowdown still
// happens.  Perhaps this slowdown is unaffected by whether the regex match
// is successful or not.
//

import std.algorithm.searching : count;
import std.range.primitives;
import std.regex;
import std.stdio;

enum testSetSize = 100000;
enum workBufferSize = 10000;

package Regex!char threadLocalRegex;
package Regex!char threadLocalRegexNoCaptures;

//static StaticRegex!char ctComplexRegex     = ctRegex!(buildComplexRegexStr(), "sxi");
//static StaticRegex!char ctCapturelessRegex = ctRegex!(buildCapturelessRegexStr(), "sxi");

static this()
{
    threadLocalRegex = buildComplexRegex();
    threadLocalRegexNoCaptures = buildCapturelessRegex();
}

auto noRegex(string toParse)
{
    // Very sloppy rough count of elements in a date string.
    // It does not matter if it works or not.
    // What does matter is that it does not allocate or use regular expressions,
    // yet still does some kind of text analysis that regular expressions
    // can be compared against.
    import std.algorithm.iteration : filter, splitter;

    auto parts = toParse.splitter(' ').filter!`!a.empty`;

    auto parseDate(string toParse)
    {
        auto bits1 = toParse.splitter('-').filter!`!a.empty`;
        if ( !bits1.empty )
            return bits1.count;
        auto bits2 = toParse.splitter('/').filter!`!a.empty`;
        return bits2.count;
    }

    auto parseTime(string toParse)
    {
        auto bits = toParse.splitter(':').filter!`!a.empty`;
        return bits.count;
    }

    if ( parts.empty )
        return 0;

    auto nBits = parseDate(parts.front);
    if ( nBits )
    {
        parts.popFront();
        if ( parts.empty )
            return nBits;
        nBits += parseTime(parts.front);
        return nBits;
    }
    else
    {
        nBits = parseTime(parts.front);
        parts.popFront();
        if ( parts.empty )
            return nBits;
        nBits += parseDate(parts.front);
        return nBits;
    }
}

auto parseNoCaptures(string toParse)
{
    // We use the regex that does not use captures, though matchFirst will
    // return at least one capture if the match succeeds: the capture of
    // the entire match.
    auto caps = toParse.matchFirst(threadLocalRegexNoCaptures);
    auto cnt = caps.count;
    assert(cnt <= 1);
    return cnt;
}

auto parseComplex(string toParse)
{
    auto caps = toParse.matchFirst(threadLocalRegex);
    return caps.count;
}
/+
auto parseNoCapturesCT(string toParse)
{
    // We use the regex that does not use captures, though matchFirst will
    // return at least one capture if the match succeeds: the capture of
    // the entire match.
    auto caps = toParse.matchFirst(ctCapturelessRegex);
    auto cnt = caps.count;
    assert(cnt <= 1);
    return cnt;
}

auto parseComplexCT(string toParse)
{
    auto caps = toParse.matchFirst(ctComplexRegex);
    return caps.count;
}
+/

struct Stats
{
    size_t total = 0;
    size_t nCalls = 0;
    size_t max = 0;

    @property size_t avg() { return total / nCalls; }

    void accumulate(size_t nCapturesOrElemss)
    {
        total += nCapturesOrElemss;
        nCalls++;
        if ( nCapturesOrElemss > max )
            max = nCapturesOrElemss;
    }
}

auto benchAndPrint(alias bench)(string name, size_t n)
{
    import core.time : TickDuration;
    import std.datetime : StopWatch;

    StopWatch sw;
    TickDuration dt;

    stdout.write("Benchmarking ", name, " ");
    sw.start();
    auto stats = bench();
    sw.stop();
    dt = sw.peek();
    stdout.writefln(" processed %s elements in %d.%0.3d seconds.", //" max == %d",
        n, dt.seconds(), dt.msecs() % 1000, stats.max);
    return stats;
}

auto pbench(alias fn)(string name, string[] testData)
{
    import std.parallelism;
    auto workUnitSize = workBufferSize/(taskPool.size*2);
    auto bench() {
        Stats stats;
        foreach( result; taskPool.map!fn(testData, workBufferSize, workUnitSize) )
            stats.accumulate(result);
        return stats;
    }
    return benchAndPrint!bench(name, testData.length);
}

auto sbench(alias fn)(string name, string[] testData)
{
    import std.algorithm.iteration : map;
    auto bench() {
        Stats stats;
        foreach( result; testData.map!fn )
            stats.accumulate(result);
        return stats;
    }
    return benchAndPrint!bench(name, testData.length);
}

void main()
{
    import std.array : array;
    import std.range;

    string[] testData = [
        "2017-08-09",
        "1983-04-16",
        "1234-32-32",
        "2017-08-09 13:12:11",
        "14:09:01.323",
        "11/29/2001",
        "13/32/9999",
        "01/01/1001"
    ];

    testData = testData.cycle.take(testSetSize).array;

    pbench!noRegex          ("non-regex parsing, parallel:               ", testData);
    pbench!parseNoCaptures  ("regex parsing, no captures, parallel:      ", testData);
    pbench!parseComplex     ("regex parsing, many captures, parallel:    ", testData);
    //pbench!parseNoCapturesCT("ct regex parsing, no captures, parallel:   ", testData);
    //pbench!parseComplexCT   ("ct regex parsing, many captures, parallel: ", testData);
    sbench!noRegex          ("non-regex parsing, serial:                 ", testData);
    sbench!parseNoCaptures  ("regex parsing, no captures, serial:        ", testData);
    sbench!parseComplex     ("regex parsing, many captures, serial:      ", testData);
    //sbench!parseNoCapturesCT("ct regex parsing, no captures, serial:     ", testData);
    //sbench!parseComplexCT   ("ct regex parsing, many captures, serial:   ", testData);
}


/// Builds a gigantic regular expression that can be used to parse addresses.
/// The result is intended to be fed into parseAddress(...).
public auto buildAddressRegex()
{
    import std.algorithm.iteration : map, uniq;
    import std.array : join;
    import std.format;
    import std.range : chain;
    import std.regex;
    import std.utf;

    enum string suffixPattern =
        chain(suffixesArray.leftColumn, suffixesArray.rightColumn.uniq).join("|");

    enum string statePattern =
        `\b(?:` ~
        chain(
            statesArray.leftColumn.map!(x => std.regex.escaper(x).toUTF8),
            statesArray.rightColumn
            ).join("|") ~
        `)\b`;

    // This one can't be executed at compile-time due to calling the replaceAll
    // method, which seems to call malloc and thus prevent itself from being
    // CTFE-able.
    string directionalPattern =
        chain(
            directionalsArray.leftColumn,
            directionalsArray.rightColumn,
            directionalsArray.rightColumn.map!(x => x.length == 1 ? x ~ `\.` : x)//std.regex.replaceAll(x, ctRegex!`(\w)`, `$1\.`))
            ).join("|");

    enum zipPattern = `\d{5}(?:-?\d{4})?`;

    enum numberPattern =
        `(?P<_numberPattern>
            ((?P<number_00>\d+)(?P<secondaryNumber_00>(-[0-9])|(\-?[A-Z]))(?=\b))   (?# Unit-attached      )
            |(?P<number_01>\d+[\-\x20]?\d+\/\d+)                                    (?# Fractional         )
            |(?P<number_02>\d+\-?\d*)                                               (?# Normal Number      )
            |(?P<number_03>[NSWE]\x20?\d+\x20?[NSWE]\x20?\d+)                       (?# Wisconsin/Illinois )
        )`;

    // This can't be executed at compile-time due to using directionalPattern.
    auto streetPattern =
        format(
            `
                (?P<_streetPattern>
                    (?P<_streetPattern_0>
                        (?# special case for addresses like 100 South Street)
                        (?P<street_00>%1$s)\W+
                        (?P<suffix_00>%2$s)\b
                    )
                    |
                    (?P<_streetPattern_1>
                        (?:(?P<predirectional_00>%1$s)\W+)?
                        (?P<_streetPattern_1_0>
                            (?P<_streetPattern_1_0_0>
                                (?P<street_01>[^,]*\d)
                                (?:[^\w,]*(?P<postdirectional_01>%1$s)\b)
                            )
                            |
                            (?P<_streetPattern_1_0_1>
                                (?P<street_02>[^,]+)
                                (?:[^\w,]+(?P<suffix_02>%2$s)\b)
                                (?:[^\w,]+(?P<postdirectional_02>%1$s)\b)?
                            )
                            |
                            (?P<_streetPattern_1_0_2>
                                (?P<street_03>[^,]+?)
                                (?:[^\w,]+(?P<suffix_03>%2$s)\b)?
                                (?:[^\w,]+(?P<postdirectional_03>%1$s)\b)?
                            )
                        )
                    )
                )
            `,
            directionalPattern,
            suffixPattern);

    enum rangedSecondaryUnitPattern =
        `(?P<secondaryUnit_00>` ~
        rangedSecondaryUnitsArray.leftColumn.join("|") ~
        `)(?![a-z])`;

    enum rangelessSecondaryUnitPattern =
        `(?P<secondaryUnit_01>` ~
        rangelessSecondaryUnitsArray.leftColumn.join("|") ~
        `)\b`;

    enum allSecondaryUnitPattern = format(
        `
            (?P<_allSecondaryUnitPattern>
                (?:[:]?
                    (?: (?:%1$s \W*)
                        | (?P<secondaryUnit_02>\#)\W*
                    )
                    (?P<secondaryNumber_02>[\w-]+)
                )
                |%2$s
            ),?
        `,
        rangedSecondaryUnitPattern,
        rangelessSecondaryUnitPattern);

    enum cityAndStatePattern = format(
        `
            (?P<_cityAndStatePattern_%%1$s>
                (?P<city_%%1$s>[^\d,]+?)\W+
                (?P<state_%%1$s>%1$s)
            )
        `,
        statePattern);

    enum placePattern = format(
        `
            (?:%1$s\W*)?
            (?:(?P<zip_%%1$s>%2$s))?
        `,
        format(cityAndStatePattern,"%1$s"),
        zipPattern);

    // This can't be executed at compile-time due to using streetPattern.
    auto addressPattern = format(
        `
            ^
            (?P<_addressPattern>
                (?P<_addressPattern_0>
                    (?# Special case for APO/FPO/DPO addresses)
                    [^\w\#]*
                    (?P<streetLine_00>.+?)
                    (?P<city_00>[AFD]PO)\W+
                    (?P<state_00>A[AEP])\W+
                    (?P<zip_00>%6$s)
                    \W*
                )
                |
                (?P<_addressPattern_1>
                    (?# Special case for PO boxes)
                    \W*
                    (?P<streetLine_01>(P[\.\x20]?O[\.\x20]?\x20)?BOX\x20[0-9]+)\W+
                    %5$s
                    \W*
                )
                |
                (?P<_addressPattern_2>
                    [^\w\#]*    (?# skip non-word chars except # {eg unit})
                    (?:%1$s)\W*
                       %2$s\W+
                    (?:%3$s\W+)?
                       %4$s
                    \W*         (?# require on non-word chars at end)
                )
            )
            $           (?# right up to end of string)
        `,
        numberPattern,
        streetPattern,
        allSecondaryUnitPattern,
        format(placePattern,"02"),
        format(placePattern,"01"),
        zipPattern);

    return addressPattern;
}

string buildComplexRegexStr()
{
    return buildAddressRegex();
}

auto buildComplexRegex()
{
    return regex(buildComplexRegexStr(), "sxi");
}

auto buildCapturelessRegexStr()
{
    //auto captureRemover = regex(`^(.*?)(P[<].*?[>])`, "si");
    //auto regexStr = replaceAll(buildComplexRegexStr(), captureRemover, ":");
    //return regexStr;
    // Can't be used at compile-time because "malloc cannot be interpreted at compile time".

    import std.exception : assumeUnique;

    auto matchCapture(string toParse)
    {
        size_t i = 0;
        if ( i+2 >= toParse.length || toParse[i..i+2] != "P<" )
            return 0;

        i += 2;
        if ( i+1 >= toParse.length )
            return 0;

        while ( i < toParse.length && toParse[i] != '>' )
            i++;

        if ( i >= toParse.length || toParse[i] != '>' )
            return 0;

        i++;
        return i;
    }

    auto complexStr = buildComplexRegexStr();
    char[] capturelessStr = new char[complexStr.length];
    size_t j = 0;
    while ( complexStr.length > 0 )
    {
        size_t i = matchCapture(complexStr);
        if (i)
        {
            capturelessStr[j++] = ':';
            complexStr = complexStr[i..$];
        }
        else
        {
            capturelessStr[j++] = complexStr[0];
            complexStr = complexStr[1..$];
        }
    }

    return capturelessStr[0..j].assumeUnique;
}

auto buildCapturelessRegex()
{
    enum regexStr = buildCapturelessRegexStr();
    //pragma(msg, "Regex without captures:\n"~regexStr~"\n");
    return regex(regexStr, "sxi");
}

// ----------------------------------------------------------------------------
// Address parser details

private
{
    /// Maps directional names (north, northeast, etc.) to abbreviations (N, NE, etc.).
    immutable string[string] directionalsAA; /// ditto

    /// Maps lowercased US state and territory names to their canonical two-letter
    /// postal abbreviations.
    immutable string[string] statesAA; /// ditto

    /// Maps lowerecased USPS standard street suffixes to their canonical postal
    /// abbreviations as found in TIGER/Line.
    immutable string[string] suffixesAA; /// ditto

    /// Secondary units that require a number after them.
    immutable string[string] rangedSecondaryUnitsAA; /// ditto

    /// Secondary units that do not require a number after them.
    immutable string[string] rangelessSecondaryUnitsAA; /// ditto
}

static this()
{
    import std.range;
    import std.stdio;

    directionalsAA             = tableToAA(directionalsArray);
    statesAA                   = tableToAA(statesArray);
    suffixesAA                 = tableToAA(suffixesArray);
    rangedSecondaryUnitsAA     = tableToAA(rangedSecondaryUnitsArray);
    rangelessSecondaryUnitsAA  = tableToAA(rangelessSecondaryUnitsArray);
}

pure private string[string] tableToAA(const string[2][] arr)
{
    string[string] result;
    foreach ( pair; arr )
        result[pair[0]] = pair[1];
    return result;
}

pure private auto leftColumn(string[][] table)
{
    import std.algorithm.iteration : map;
    return table.map!`a[0]`;
}

pure private auto rightColumn(string[][] table)
{
    import std.algorithm.iteration : map;
    return table.map!`a[$-1]`;
}

private:

/// Maps directional names (north, northeast, etc.) to abbreviations (N, NE, etc.).
enum string[2][] directionalsArray = [
    ["NORTH", "N"],
    ["NORTHEAST", "NE"],
    ["EAST", "E"],
    ["SOUTHEAST", "SE"],
    ["SOUTH", "S"],
    ["SOUTHWEST", "SW"],
    ["WEST", "W"],
    ["NORTHWEST", "NW"]];

/// Secondary units that do not require a number after them.
enum string[2][] rangelessSecondaryUnitsArray = [
    ["BA?SE?ME?N?T", "BSMT"],
    ["FRO?NT", "FRNT"],
    ["LO?BBY", "LBBY"],
    ["LOWE?R", "LOWR"],
    ["OFF?I?CE?", "OFC"],
    ["PE?N?T?HO?U?S?E?", "PH"],
    ["REAR", "REAR"],
    ["SIDE", "SIDE"],
    ["UPPE?R", "UPPR"]];

/// Secondary units that require a number after them.
enum string[2][] rangedSecondaryUnitsArray = [
    ["SU?I?TE", "STE"],
    ["(?:AP)(?:AR)?T(?:ME?NT)?", "APT"],
    ["(?:DEP)(?:AR)?T(?:ME?NT)?", "DEPT"],
    ["RO*M", "RM"],
    ["FLO*R?", "FL"],
    ["UNI?T", "UNIT"],
    ["BU?I?LDI?N?G", "BLDG"],
    ["HA?NGA?R", "HNGR"],
    ["KEY", "KEY"],
    ["LO?T", "LOT"],
    ["PIER", "PIER"],
    ["SLIP", "SLIP"],
    ["SPA?CE?", "SPACE"],
    ["STOP", "STOP"],
    ["TRA?I?LE?R", "TRLR"],
    ["BOX", "BOX"]];


/// Maps lowercased US state and territory names to their canonical two-letter
/// postal abbreviations.
enum string[2][] statesArray = [
    ["ALABAMA", "AL"],
    ["ALASKA", "AK"],
    ["AMERICAN SAMOA", "AS"],
    ["ARIZONA", "AZ"],
    ["ARKANSAS", "AR"],
    ["CALIFORNIA", "CA"],
    ["COLORADO", "CO"],
    ["CONNECTICUT", "CT"],
    ["DELAWARE", "DE"],
    ["DISTRICT OF COLUMBIA", "DC"],
    ["FEDERATED STATES OF MICRONESIA", "FM"],
    ["FLORIDA", "FL"],
    ["GEORGIA", "GA"],
    ["GUAM", "GU"],
    ["HAWAII", "HI"],
    ["IDAHO", "ID"],
    ["ILLINOIS", "IL"],
    ["INDIANA", "IN"],
    ["IOWA", "IA"],
    ["KANSAS", "KS"],
    ["KENTUCKY", "KY"],
    ["LOUISIANA", "LA"],
    ["MAINE", "ME"],
    ["MARSHALL ISLANDS", "MH"],
    ["MARYLAND", "MD"],
    ["MASSACHUSETTS", "MA"],
    ["MICHIGAN", "MI"],
    ["MINNESOTA", "MN"],
    ["MISSISSIPPI", "MS"],
    ["MISSOURI", "MO"],
    ["MONTANA", "MT"],
    ["NEBRASKA", "NE"],
    ["NEVADA", "NV"],
    ["NEW HAMPSHIRE", "NH"],
    ["NEW JERSEY", "NJ"],
    ["NEW MEXICO", "NM"],
    ["NEW YORK", "NY"],
    ["NORTH CAROLINA", "NC"],
    ["NORTH DAKOTA", "ND"],
    ["NORTHERN MARIANA ISLANDS", "MP"],
    ["OHIO", "OH"],
    ["OKLAHOMA", "OK"],
    ["OREGON", "OR"],
    ["PALAU", "PW"],
    ["PENNSYLVANIA", "PA"],
    ["PUERTO RICO", "PR"],
    ["RHODE ISLAND", "RI"],
    ["SOUTH CAROLINA", "SC"],
    ["SOUTH DAKOTA", "SD"],
    ["TENNESSEE", "TN"],
    ["TEXAS", "TX"],
    ["UTAH", "UT"],
    ["VERMONT", "VT"],
    ["VIRGIN ISLANDS", "VI"],
    ["VIRGINIA", "VA"],
    ["WASHINGTON", "WA"],
    ["WEST VIRGINIA", "WV"],
    ["WISCONSIN", "WI"],
    ["WYOMING", "WY"]];


/// Maps lowerecased USPS standard street suffixes to their canonical postal
/// abbreviations as found in TIGER/Line.
enum string[2][] suffixesArray = [
    ["ALLEE", "ALY"],
    ["ALLEY", "ALY"],
    ["ALLY", "ALY"],
    ["ANEX", "ANX"],
    ["ANNEX", "ANX"],
    ["ANNX", "ANX"],
    ["ARCADE", "ARC"],
    ["AV", "AVE"],
    ["AVEN", "AVE"],
    ["AVENU", "AVE"],
    ["AVENUE", "AVE"],
    ["AVN", "AVE"],
    ["AVNUE", "AVE"],
    ["BAYOO", "BYU"],
    ["BAYOU", "BYU"],
    ["BEACH", "BCH"],
    ["BEND", "BND"],
    ["BLUF", "BLF"],
    ["BLUFF", "BLF"],
    ["BLUFFS", "BLFS"],
    ["BOT", "BTM"],
    ["BOTTM", "BTM"],
    ["BOTTOM", "BTM"],
    ["BOUL", "BLVD"],
    ["BOULEVARD", "BLVD"],
    ["BOULV", "BLVD"],
    ["BRANCH", "BR"],
    ["BRDGE", "BRG"],
    ["BRIDGE", "BRG"],
    ["BRNCH", "BR"],
    ["BROOK", "BRK"],
    ["BROOKS", "BRKS"],
    ["BURG", "BG"],
    ["BURGS", "BGS"],
    ["BYPA", "BYP"],
    ["BYPAS", "BYP"],
    ["BYPASS", "BYP"],
    ["BYPS", "BYP"],
    ["CAMP", "CP"],
    ["CANYN", "CYN"],
    ["CANYON", "CYN"],
    ["CAPE", "CPE"],
    ["CAUSEWAY", "CSWY"],
    ["CAUSWAY", "CSWY"],
    ["CEN", "CTR"],
    ["CENT", "CTR"],
    ["CENTER", "CTR"],
    ["CENTERS", "CTRS"],
    ["CENTR", "CTR"],
    ["CENTRE", "CTR"],
    ["CIRC", "CIR"],
    ["CIRCL", "CIR"],
    ["CIRCLE", "CIR"],
    ["CIRCLES", "CIRS"],
    ["CK", "CRK"],
    ["CLIFF", "CLF"],
    ["CLIFFS", "CLFS"],
    ["CLUB", "CLB"],
    ["CMP", "CP"],
    ["CNTER", "CTR"],
    ["CNTR", "CTR"],
    ["CNYN", "CYN"],
    ["COMMON", "CMN"],
    ["CORNER", "COR"],
    ["CORNERS", "CORS"],
    ["COURSE", "CRSE"],
    ["COURT", "CT"],
    ["COURTS", "CTS"],
    ["COVE", "CV"],
    ["COVES", "CVS"],
    ["CR", "CRK"],
    ["CRCL", "CIR"],
    ["CRCLE", "CIR"],
    ["CRECENT", "CRES"],
    ["CREEK", "CRK"],
    ["CRESCENT", "CRES"],
    ["CRESENT", "CRES"],
    ["CREST", "CRST"],
    ["CROSSING", "XING"],
    ["CROSSROAD", "XRD"],
    ["CRSCNT", "CRES"],
    ["CRSENT", "CRES"],
    ["CRSNT", "CRES"],
    ["CRSSING", "XING"],
    ["CRSSNG", "XING"],
    ["CRT", "CT"],
    ["CURVE", "CURV"],
    ["DALE", "DL"],
    ["DAM", "DM"],
    ["DIV", "DV"],
    ["DIVIDE", "DV"],
    ["DRIV", "DR"],
    ["DRIVE", "DR"],
    ["DRIVES", "DRS"],
    ["DRV", "DR"],
    ["DVD", "DV"],
    ["ESTATE", "EST"],
    ["ESTATES", "ESTS"],
    ["EXP", "EXPY"],
    ["EXPR", "EXPY"],
    ["EXPRESS", "EXPY"],
    ["EXPRESSWAY", "EXPY"],
    ["EXPW", "EXPY"],
    ["EXTENSION", "EXT"],
    ["EXTENSIONS", "EXTS"],
    ["EXTN", "EXT"],
    ["EXTNSN", "EXT"],
    ["FALLS", "FLS"],
    ["FERRY", "FRY"],
    ["FIELD", "FLD"],
    ["FIELDS", "FLDS"],
    ["FLAT", "FLT"],
    ["FLATS", "FLTS"],
    ["FORD", "FRD"],
    ["FORDS", "FRDS"],
    ["FOREST", "FRST"],
    ["FORESTS", "FRST"],
    ["FORG", "FRG"],
    ["FORGE", "FRG"],
    ["FORGES", "FRGS"],
    ["FORK", "FRK"],
    ["FORKS", "FRKS"],
    ["FORT", "FT"],
    ["FREEWAY", "FWY"],
    ["FREEWY", "FWY"],
    ["FRRY", "FRY"],
    ["FRT", "FT"],
    ["FRWAY", "FWY"],
    ["FRWY", "FWY"],
    ["GARDEN", "GDN"],
    ["GARDENS", "GDNS"],
    ["GARDN", "GDN"],
    ["GATEWAY", "GTWY"],
    ["GATEWY", "GTWY"],
    ["GATWAY", "GTWY"],
    ["GLEN", "GLN"],
    ["GLENS", "GLNS"],
    ["GRDEN", "GDN"],
    ["GRDN", "GDN"],
    ["GRDNS", "GDNS"],
    ["GREEN", "GRN"],
    ["GREENS", "GRNS"],
    ["GROV", "GRV"],
    ["GROVE", "GRV"],
    ["GROVES", "GRVS"],
    ["GTWAY", "GTWY"],
    ["HARB", "HBR"],
    ["HARBOR", "HBR"],
    ["HARBORS", "HBRS"],
    ["HARBR", "HBR"],
    ["HAVEN", "HVN"],
    ["HAVN", "HVN"],
    ["HEIGHT", "HTS"],
    ["HEIGHTS", "HTS"],
    ["HGTS", "HTS"],
    ["HIGHWAY", "HWY"],
    ["HIGHWY", "HWY"],
    ["HILL", "HL"],
    ["HILLS", "HLS"],
    ["HIWAY", "HWY"],
    ["HIWY", "HWY"],
    ["HLLW", "HOLW"],
    ["HOLLOW", "HOLW"],
    ["HOLLOWS", "HOLW"],
    ["HOLWS", "HOLW"],
    ["HRBOR", "HBR"],
    ["HT", "HTS"],
    ["HWAY", "HWY"],
    ["INLET", "INLT"],
    ["ISLAND", "IS"],
    ["ISLANDS", "ISS"],
    ["ISLES", "ISLE"],
    ["ISLND", "IS"],
    ["ISLNDS", "ISS"],
    ["JCTION", "JCT"],
    ["JCTN", "JCT"],
    ["JCTNS", "JCTS"],
    ["JUNCTION", "JCT"],
    ["JUNCTIONS", "JCTS"],
    ["JUNCTN", "JCT"],
    ["JUNCTON", "JCT"],
    ["KEY", "KY"],
    ["KEYS", "KYS"],
    ["KNOL", "KNL"],
    ["KNOLL", "KNL"],
    ["KNOLLS", "KNLS"],
    ["LA", "LN"],
    ["LAKE", "LK"],
    ["LAKES", "LKS"],
    ["LANDING", "LNDG"],
    ["LANE", "LN"],
    ["LANES", "LN"],
    ["LDGE", "LDG"],
    ["LIGHT", "LGT"],
    ["LIGHTS", "LGTS"],
    ["LNDNG", "LNDG"],
    ["LOAF", "LF"],
    ["LOCK", "LCK"],
    ["LOCKS", "LCKS"],
    ["LODG", "LDG"],
    ["LODGE", "LDG"],
    ["LOOPS", "LOOP"],
    ["MANOR", "MNR"],
    ["MANORS", "MNRS"],
    ["MEADOW", "MDW"],
    ["MEADOWS", "MDWS"],
    ["MEDOWS", "MDWS"],
    ["MILL", "ML"],
    ["MILLS", "MLS"],
    ["MISSION", "MSN"],
    ["MISSN", "MSN"],
    ["MNT", "MT"],
    ["MNTAIN", "MTN"],
    ["MNTN", "MTN"],
    ["MNTNS", "MTNS"],
    ["MOTORWAY", "MTWY"],
    ["MOUNT", "MT"],
    ["MOUNTAIN", "MTN"],
    ["MOUNTAINS", "MTNS"],
    ["MOUNTIN", "MTN"],
    ["MSSN", "MSN"],
    ["MTIN", "MTN"],
    ["NECK", "NCK"],
    ["ORCHARD", "ORCH"],
    ["ORCHRD", "ORCH"],
    ["OVERPASS", "OPAS"],
    ["OVL", "OVAL"],
    ["PARKS", "PARK"],
    ["PARKWAY", "PKWY"],
    ["PARKWAYS", "PKWY"],
    ["PARKWY", "PKWY"],
    ["PASSAGE", "PSGE"],
    ["PATHS", "PATH"],
    ["PIKES", "PIKE"],
    ["PINE", "PNE"],
    ["PINES", "PNES"],
    ["PK", "PARK"],
    ["PKWAY", "PKWY"],
    ["PKWYS", "PKWY"],
    ["PKY", "PKWY"],
    ["PLACE", "PL"],
    ["PLAIN", "PLN"],
    ["PLAINES", "PLNS"],
    ["PLAINS", "PLNS"],
    ["PLAZA", "PLZ"],
    ["PLZA", "PLZ"],
    ["POINT", "PT"],
    ["POINTS", "PTS"],
    ["PORT", "PRT"],
    ["PORTS", "PRTS"],
    ["PRAIRIE", "PR"],
    ["PRARIE", "PR"],
    ["PRK", "PARK"],
    ["PRR", "PR"],
    ["RAD", "RADL"],
    ["RADIAL", "RADL"],
    ["RADIEL", "RADL"],
    ["RANCH", "RNCH"],
    ["RANCHES", "RNCH"],
    ["RAPID", "RPD"],
    ["RAPIDS", "RPDS"],
    ["RDGE", "RDG"],
    ["REST", "RST"],
    ["RIDGE", "RDG"],
    ["RIDGES", "RDGS"],
    ["RIVER", "RIV"],
    ["RIVR", "RIV"],
    ["RNCHS", "RNCH"],
    ["ROAD", "RD"],
    ["ROADS", "RDS"],
    ["ROUTE", "RTE"],
    ["RVR", "RIV"],
    ["SHOAL", "SHL"],
    ["SHOALS", "SHLS"],
    ["SHOAR", "SHR"],
    ["SHOARS", "SHRS"],
    ["SHORE", "SHR"],
    ["SHORES", "SHRS"],
    ["SKYWAY", "SKWY"],
    ["SPNG", "SPG"],
    ["SPNGS", "SPGS"],
    ["SPRING", "SPG"],
    ["SPRINGS", "SPGS"],
    ["SPRNG", "SPG"],
    ["SPRNGS", "SPGS"],
    ["SPURS", "SPUR"],
    ["SQR", "SQ"],
    ["SQRE", "SQ"],
    ["SQRS", "SQS"],
    ["SQU", "SQ"],
    ["SQUARE", "SQ"],
    ["SQUARES", "SQS"],
    ["STATION", "STA"],
    ["STATN", "STA"],
    ["STN", "STA"],
    ["STR", "ST"],
    ["STRAV", "STRA"],
    ["STRAVE", "STRA"],
    ["STRAVEN", "STRA"],
    ["STRAVENUE", "STRA"],
    ["STRAVN", "STRA"],
    ["STREAM", "STRM"],
    ["STREET", "ST"],
    ["STREETS", "STS"],
    ["STREME", "STRM"],
    ["STRT", "ST"],
    ["STRVN", "STRA"],
    ["STRVNUE", "STRA"],
    ["SUMIT", "SMT"],
    ["SUMITT", "SMT"],
    ["SUMMIT", "SMT"],
    ["TERR", "TER"],
    ["TERRACE", "TER"],
    ["THROUGHWAY", "TRWY"],
    ["TPK", "TPKE"],
    ["TR", "TRL"],
    ["TRACE", "TRCE"],
    ["TRACES", "TRCE"],
    ["TRACK", "TRAK"],
    ["TRACKS", "TRAK"],
    ["TRAFFICWAY", "TRFY"],
    ["TRAIL", "TRL"],
    ["TRAILS", "TRL"],
    ["TRK", "TRAK"],
    ["TRKS", "TRAK"],
    ["TRLS", "TRL"],
    ["TRNPK", "TPKE"],
    ["TRPK", "TPKE"],
    ["TUNEL", "TUNL"],
    ["TUNLS", "TUNL"],
    ["TUNNEL", "TUNL"],
    ["TUNNELS", "TUNL"],
    ["TUNNL", "TUNL"],
    ["TURNPIKE", "TPKE"],
    ["TURNPK", "TPKE"],
    ["UNDERPASS", "UPAS"],
    ["UNION", "UN"],
    ["UNIONS", "UNS"],
    ["VALLEY", "VLY"],
    ["VALLEYS", "VLYS"],
    ["VALLY", "VLY"],
    ["VDCT", "VIA"],
    ["VIADCT", "VIA"],
    ["VIADUCT", "VIA"],
    ["VIEW", "VW"],
    ["VIEWS", "VWS"],
    ["VILL", "VLG"],
    ["VILLAG", "VLG"],
    ["VILLAGE", "VLG"],
    ["VILLAGES", "VLGS"],
    ["VILLE", "VL"],
    ["VILLG", "VLG"],
    ["VILLIAGE", "VLG"],
    ["VIST", "VIS"],
    ["VISTA", "VIS"],
    ["VLLY", "VLY"],
    ["VST", "VIS"],
    ["VSTA", "VIS"],
    ["WALKS", "WALK"],
    ["WELL", "WL"],
    ["WELLS", "WLS"],
    ["WY", "WAY"]];