Home > Backend Development > PHP Tutorial > 字符串 - PHP短文本匹配的排序算法

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

WBOY
Release: 2016-06-06 20:41:53
Original
1040 people have browsed it

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

<code><?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  $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('无'));
</code>
Copy after login
Copy after login

回复内容:

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

<code><?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  $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('无'));
</code>
Copy after login
Copy after login

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

<code><?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);
</code>
Copy after login
Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template