Сложные сравнения строк

Question

Я пытаюсь написать функцию в PHP, которая принимает массив строк (needle) и выполняет сравнение с другим массивом строк (haystack). Цель этой функции - быстро доставить подходящие строки для поиска AJAX, поэтому она должна быть максимально быстрой.

Вот пример кода для иллюстрации двух массивов;

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

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

Хотя это само по себе довольно просто, цель сравнения - подсчитать, сколько строк needle появляется в haystack.

Однако есть три ограничения;

1. Сравнение не чувствительно к регистру
2. needle должен соответствовать только символам на начало слова. Например, «hote» будет соответствовать «Hotel», но «Resta» не будет соответствовать "Errestas".
3. Мы хотим посчитать количество подходящих needles, а не количество needle появлений. Если место называется «Hotel Hotel Hotel», нам нужно, чтобы результат был 1, а не 3.

Используя приведенный выше пример, мы ожидаем в результате следующий ассоциативный массив:

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

Я пытался реализовать функцию для этого, используя preg_match_all() и регулярное выражение, которое выглядит как /(\A|\s)(ba|hot|resta)/. Хотя это гарантирует, что мы сопоставляем только начало слов, оно не учитывает строки, которые содержат одинаковые needle дважды.

Я отправляю сообщение, чтобы узнать, есть ли у кого-то еще решение?

Answer 1

Я нашел, что вы достаточно подробно описали проблему, чтобы я мог использовать подход TDD для ее решения. Итак, поскольку я очень стараюсь быть парнем TDD, я написал тесты и функцию, чтобы тесты прошли. Наименования могут быть не идеальными, но их легко изменить. Алгоритм функции также может быть не самым лучшим, но теперь, когда есть тесты, рефакторинг должен быть очень простым и безболезненным.

Вот тесты:

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);
    }
}

А вот и функция:

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;
}

Проверка необходимости оператора break

Следующий тест показывает, когда необходимо break. Запустите этот тест как с оператором break, так и без него внутри функции match.

/**
 * 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 2

функции массива и строки, как правило, быстрее по величинам, чем регулярные выражения. Это должно быть довольно легко сделать то, что вы хотите с комбинацией array_filter и substr_count .

Приветствия

Answer 3

@ Ionut G. Stan Ого, какой ответ!

@ Лахлан Макдональд Если у вас есть проблемы со скоростью (попробуйте сначала, а не просто предполагайте :)), вы можете использовать, чтобы стрелка соответствовала началу строки: разбить стог сена в процессе сборки по первой букве и выполнить итерацию только массива сена, соответствующего первой Обугленная игла.

Будет сделано менее 1/10 сравнения на иглу.

Answer 4

Вы можете попробовать:

$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;
}