Complex String Comparisons

Question

I'm trying to write a function in PHP that takes an array of strings (needle) and performs a comparison against another array of strings (haystack). The purpose of this function is to quickly deliver matching strings for an AJAX search, so it needs to be as fast as possible.

Here's some sample code to illustrate the two arrays;

$needle = array('ba','hot','resta');

$haystack = array(
    'Southern Hotel',
    'Grange Restaurant & Hotel',
    'Austral Hotel',
    'Barsmith Hotel',
    'Errestas'
);

Whilst this is quite easy in itself, the aim of the comparison is to count how many of the needle strings appear in the haystack.

However, there are three constraints;

1. The comparison is case-insensitive
2. The needle must only match characters at the beginning of the word. For example, "hote" will match "Hotel", but "resta" will not match "Errestas".
3. We want to count the number of matching needles, not the number of needle appearances. If a place is named "Hotel Hotel Hotel", we need the result to be 1 not 3.

Using the above example, we'd expect the following associative array as a result:

$haystack = array(
    'Southern Hotel' => 1,
    'Grange Restaurant & Hotel' => 2,
    'Austral Hotel' => 1,
    'Barsmith Hotel' => 2,
    'Erresta'  => 0
);

I've been trying to implement a function to do this, using a preg_match_all() and a regexp which looks like /(\A|\s)(ba|hot|resta)/. Whilst this ensures we only match the beginning of words, it doesn't take into account strings which contain the same needle twice.

I am posting to see whether someone else has a solution?

Answer 1

Hi,

array and string functions are usually faster by magnitudes than regexps. It should be fairly easy to do what you want with a combination of array_filter and substr_count.

Cheers,

Answer 2

I've found you're description of the problem detailed enough that I could take a TDD approach for solving it. So, because I'm so much trying to be a TDD guy, I've wrote the tests and the function to make the tests pass. Namings might not be perfect, but they're easily changeable. The algorithm of the function may also not be the best, but now that there are tests, refactoring should be very easy and painless.

Here are the tests:

class MultiMatcherTest extends PHPUnit_Framework_TestCase
{
    public function testTheComparisonIsCaseInsensitive()
    {
        $needles  = array('hot');
        $haystack = array('Southern Hotel');
        $result   = match($needles, $haystack);

        $this->assertEquals(array('Southern Hotel' => 1), $result);
    }

    public function testNeedleMatchesOnlyCharsAtBeginningOfWord()
    {
        $needles  = array('resta');
        $haystack = array('Errestas');
        $result   = match($needles, $haystack);

        $this->assertEquals(array('Errestas' => 0), $result);
    }

    public function testMatcherCountsNeedlesNotOccurences()
    {
        $needles  = array('hot');
        $haystack = array('Southern Hotel', 'Grange Restaurant & Hotel');
        $expected = array('Southern Hotel'            => 1,
                          'Grange Restaurant & Hotel' => 1);
        $result   = match($needles, $haystack);

        $this->assertEquals($expected, $result);
    }

    public function testAcceptance()
    {
        $needles  = array('ba','hot','resta');
        $haystack = array(
            'Southern Hotel',
            'Grange Restaurant & Hotel',
            'Austral Hotel',
            'Barsmith Hotel',
            'Errestas',
        );
        $expected = array(
            'Southern Hotel'            => 1,
            'Grange Restaurant & Hotel' => 2,
            'Austral Hotel'             => 1,
            'Barsmith Hotel'            => 2,
            'Errestas'                  => 0,
        );

        $result = match($needles, $haystack);

        $this->assertEquals($expected, $result);
    }
}

And here's the function:

function match($needles, $haystack)
{
    // The default result will containg 0 (zero) occurences for all $haystacks
    $result = array_combine($haystack, array_fill(0, count($haystack), 0));

    foreach ($needles as $needle) {

        foreach ($haystack as $subject) {
            $words = str_word_count($subject, 1); // split into words

            foreach ($words as $word) {
                if (stripos($word, $needle) === 0) {
                    $result[$subject]++;

                    break;
                }
            }
        }
    }

    return $result;
}

Testing that the break statement is necessary

The following test shows when break is necessary. Run this test both with and without a break statement inside the match function.

/**
 * This test demonstrates the purpose of the BREAK statement in the
 * implementation function. Without it, the needle will be matched twice.
 * "hot" will be matched for each "Hotel" word.
 */
public function testMatcherCountsNeedlesNotOccurences2()
{
    $needles  = array('hot');
    $haystack = array('Southern Hotel Hotel');
    $expected = array('Southern Hotel Hotel' => 1);
    $result   = match($needles, $haystack);

    $this->assertEquals($expected, $result);
}

Answer 3

You could try:

$results=Array();
foreach ($haystack as $stack) {
 $counter=0;
 $lcstack=strtolower($stack);
 foreach ($needle as $need) {
  if (substr($lcstack,0,strlen($need))==strtolower($need)) {
   $counter++;
  }
 }
 $results[$stack]=$counter;
}

Answer 4

@Ionut G. Stan wow, what an answer!

@Lachlan McDonald If you have speed concerns (try it first, not just assume:) ) you can use that the needle should match the beginning of the string: splitting the haystack during the build process by the first letter and iterate only the haystack array matching the first char of the needle.

It will make less than 1/10th comparisons per needle.