字符串 - PHP短文本匹配的排序算法

Question

PHP做简单的短文本搜索匹配时，我用的是最长公共子序列。但是如果关键字匹配到两条文本的相似度一样时，如何将两条文本中关键字更靠前的返回？举例：关键字“无”匹配到“无双”和“虚无”，我要如何在返回的结果中把“无双”排在“虚无”前面？那“无双”匹配到的“无小明的双”和“小明无的双”呢？

<?php
$names = array(
  '真三国无双',
  '无双剑姬',
  '虚无',
  '一时无两',
  '南无阿弥陀佛',
  '崖山之后无中国',
);

//拆分词语为单个字符
function split_name($name) {
  preg_match_all("/./u", $name, $arr);
  return $arr[0];
}

//最长公共子序列
function LCS($str_1, $str_2) {
  $len_1 = strlen($str_1);
  $len_2 = strlen($str_2);
  $len = $len_1 > $len_2 ? $len_1 : $len_2;

  $dp = array();
  for ($i = 0; $i <= $len; $i++) {
    $dp[$i] = array();
    $dp[$i][0] = 0;
    $dp[0][$i] = 0;
  }

  for ($i = 1; $i <= $len_1; $i++) {
    for ($j = 1; $j <= $len_2; $j++) {
      if ($str_1[$i - 1] == $str_2[$j - 1]) {
        $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
      } else {
        $dp[$i][$j] = $dp[$i - 1][$j] > $dp[$i][$j - 1] ? $dp[$i - 1][$j] : $dp[$i][$j - 1];
      }
    }
  }

  return $dp[$len_1][$len_2];
}

function search($name) {
  Global $names;

  $sort_list = array();
  if (mb_strlen($name, 'utf-8') != strlen($name)) { // 是否全英文字符
    $arr_1 = array_unique(split_name($name));
    foreach ($names as $value) {
      $arr_2 = array_unique(split_name($value));
      $similarity = count($arr_2) - count(array_diff($arr_2, $arr_1));
      $sort_list[$value] = $similarity;
    }
  } else {
    foreach ($names as $value) {
      $similarity = LCS($name, $value);
      $sort_list[$value] = $similarity;
    }
  }
  arsort($sort_list);

  return $sort_list;
}

header('content-type:text/html;charset=utf-8');
print_r(search('无'));

Answer 1

所以你只是想让搜索结果中字在前的排名越前咯？那不就直接把所有匹配到的字的位置相加越小的不就在前面么？不知道我理解错没有... 代码在线运行：http://3v4l.org/K0X7m

<?php
/** 初始化设置查询关键词和查询内容 **/
$names = array(
  '真三国无双',
  '无双剑姬',
  '虚无',
  '一时无两',
  '南无阿弥陀佛',
  '崖山之后无中国',
);
$search = array("无","双");

/** 劈开字符串 **/
$res = array();
foreach($names as $name) {
    preg_match_all("/./u", $name, $match);
    $res[$name]['single'] = $match[0];
}

/** 对字符串进行遍历，存储匹配到的位置，对没有匹配到所有的关键词的字符串剔除，匹配到所有的将位置相加，越小的排名越靠前 **/
foreach($res as $name => $v) {
    $pos = array();
    foreach($v['single'] as $k => $s) {
        if(in_array($s, $search)) $pos[$s][] = $k;
    }
    if(count($pos) != count($search)) {
        unset($res[$name]);
    } else {
        $seq = 0;
        array_walk_recursive($pos, function($i) use(&$seq) {
            $seq += $i;
        });
        $res[$name] = $seq;
    }
}

ksort($res);
$res = array_keys($res);

var_dump($res);