Nguyên lý hoạt động similar_text trong PHP string

WyNotMe · April 3, 2019, 12:11am

Em mới lân la sang PHP string có thấy similar_text() function được sử dụng để tính toán trả về độ tương tự giữa 2 chuỗi. Theo em hiểu thì là trả về số ký tự trùng khớp giữa 2 chuỗi nhưng thực tế thì em thấy không phải như vậy. Ví dụ:

$str1 = "abcdef";
$str2 = "abcmfed";

Nếu bình thường thì nhìn vào sẽ nghĩ hàm similar_text() sẽ trả về 6 vì 2 chuỗi này trùng nhau 6 ký tự.
Nhưng khi chạy thì hàm lại trả về 4.
Mong mn ai biết thông não giúp em nguyên lý so sánh của similar_text giúp em được không ạ?
Với em có tìm hiểu trên mạng có thấy việc đổi chỗ giữa 2 tham số str1 và $str2 có khả năng dẫn đến kết quả khác nhau.
Kiểu như similar_text("bafoobar", "barfoo") => trả về 5
Nhưng similar_text("barfoo", "bafoobar") => trả về 3.

Ai biết lý giải giúp em luôn với ạ. Em cảm ơn trước.

hungaya · April 2, 2019, 7:26am

Đoán mò, similar_text trả về độ dài của dãy con chung dài nhất.

Bạn chạy mấy chuỗi trên chưa nhỉ?

echo similar_text("abcdef", "abcmfed")."\n"; // 4 - abce
echo similar_text("bafoobar", "barfoo")."\n"; // 5 - bafoo
echo similar_text("barfoo", "barfoobar")."\n"; // 6 - barfoo

rogp10 · April 2, 2019, 7:39am

Hàm này còn có một vấn đề lớn.

similar_text(s1, s2) != similar_text(s2, s1)

=> ko nên dùng vì nó không có căn cứ gì cả.

Thay vào đó ta dùng https://www.php.net/manual/en/function.levenshtein.php

WyNotMe · April 2, 2019, 7:36am

Tay nhanh hơn não ạ =))

WyNotMe · April 2, 2019, 7:38am

Mình cũng thắc mắc cái này ở dưới

hungaya · April 2, 2019, 3:08pm

Implementation (nguyên lý hoạt động) có thể như vầy:

function similarTextCount($str1, $str2)
{	
	$len1 = strlen($str1);
	$len2 = strlen($str2);
	
	$i = 0; $j = 0;
	$count = 0;
	while ($i < $len1 && $j < $len2) {
		if ($str1[$i] == $str2[$j]) {
			$count++;
			$i++;
		}
		$j++;
	}
	
	return $count;
}

WyNotMe · April 2, 2019, 8:03am

Lý giải của anh rất hay ạ! Em cảm ơn =)) Như vậy similar_text(“abcdef”, “abcmfed”) trả về 4 nhưng mà là abcd chứ không phải abce anh nhỉ Em cảm ơn anh lần nữa

WyNotMe · April 2, 2019, 8:46am

Anh ơi! Nguyên lý trên của anh hoạt động tốt với những ví dụ ở trên bài post. Tuy nhiên

similar_text("PHP IS GREAT", "WITH MYSQL"); // Trả về 3

Nhưng theo nguyên tắc của function anh tạo ra thì lại trả về 0. Anh có thể giúp em thêm không ạ?

hungaya · April 2, 2019, 3:15pm

Sau khi xem lại, nó hiện thực hơi khác, không phải là đếm chiều dài dãy con chung dài nhất.
Nó liệt kê tất cả dãy con chung dài nhất, dài nhì, dài ba,… Mỗi dãy có chiều lần lượt l₁, l₂, l₃,…
Kết quả trả về: l₁ + l₂ + l₃ + …

Cách liệt kê hơi bị quái dị, mình viết lại mã giả như sau, giả sử input là $str1 và $str2:

Khởi tạo: biến sum đếm tổng số dãy con chung có độ dài lớn nhất, giá trị 0.
Bước 1: Tìm dãy con chung dài nhất, nếu có nhiều dãy con có cùng độ dài lớn nhất thì chọn dãy nằm bên trái. Biến sum được cộng thêm chiều dài của dãy chung được chọn.
- Nằm bên trái là có dãy chung có index trong $str1 nhỏ nhất. Nếu có nhiều dãy chung có giá trị index trong $str1 bằng nhau thì lấy dãy chung có index trong $str2 nhỏ nhất.
Bước 2: Cắt 2 chuỗi từ đầu chuỗi đến cuối đoạn dãy chung, thực hiện bước 1 cho 2 chuỗi mới.

Viết có vẻ khó hiểu (mình đọc cũng chả hiểu ), nên làm ví dụ cho dễ hiểu:

         012345678901
-----------------------
$str1 = 'PHP IS GREAT';
$str2 = 'WITH MYSQL';

Bước 1:
Sau khi mò các kiểu, chỉ thấy dãy chung của $str1 và $str2 có độ dài lớn nhất là 1: (’ ’ là space)

	$str1	$str2
‘H’	1	3
’ ’	3	4
’ ’	6	4
‘S’	5	7
‘T’	11	2

Trong 5 dãy trên, chỉ dãy ‘H’ có index $str1 là nhỏ nhất nên được chọn là dãy chung.
sum = sum_old + 1 = 0 + 1 = 1

Bước 2:
Cắt chuỗi $str1. ([…] là dãy chung, | là chỗ cắt chuỗi)

'PHP IS GREAT' --> 'P[H]|P IS GREAT' --> 'P IS GREAT'
$str1 = 'P IS GREAT';

Cắt chuỗi $str2.

'WITH MYSQL' --> 'WIT[H]| MYSQL' --> ' MYSQL'
$str2 = ' MYSQL'; // có space trước MYSQL

Bước 1:

         0123456789
--------------------
$str1 = 'P IS GREAT';
$str2 = ' MYSQL';

Dãy con chung có chiều dài lớn nhất là 1

	$str1	$str2
’ ’	1	0
’ ’	4	0
‘S’	3	3

Dãy ’ ’ được chọn vì index $str1 nhỏ nhất, bằng 1
sum = sum_old + 1 = 1 + 1 = 2

Bước 2:
Cắt chuỗi $str1

'P IS GREAT' --> 'P[ ]|IS GREAT' --> 'IS GREAT'
$str1 = 'IS GREAT';

Cắt chuỗi $str2

' MYSQL' --> '[ ]|MYSQL' --> 'MYSQL'
$str2 = 'MYSQL';

Bước 1:

         01234567
------------------
$str1 = 'IS GREAT';
$str2 = 'MYSQL';

Dãy con chung có chiều dài lớn nhất là 1

	$str1	$str2
‘S’	1	2

Dãy chung ‘S’ có độ dài 1 được chọn.
sum = sum_old + 1 = 2 + 1 = 3

Bước 2:
Cắt chuỗi $str1

'IS GREAT' --> 'I[S]| GREAT' --> ' GREAT'
$str1 = ' GREAT';

Cắt chuỗi $str2

'MYSQL' --> 'MY[S]|QL' --> 'QL'
$str2 = 'QL';

Bước 1:

         012345
-----------------
$str1 = ' GREAT';
$str2 = 'QL';

Hai dãy trên không có dãy chung.

Kết luận: Trả về giá trị sum = 3.

Phần sau là code hiện thực, bấm nút mũi tên để xem thêm.

Function php_similar_str() trả về chuỗi con chung dài nhất.

Input:

txt1, len1: pointer trỏ tới địa chỉ đầu tiên chuỗi thứ nhất và chiều dài của nó.
txt2, len2: pointer và chiều dài của chuỗi thứ 2, tương tự như trên.

Output:

pos1: pointer trỏ đến dãy con chung trong chuỗi đầu tiên.
pos2: pointer trở đến dãy con chung trong chuỗi thứ hai.
max: chiều dài của dãy con.

Local variable:

p, q: pointer hiện tại (current pointer), dùng trong vòng lặp for.
end1: pointer trỏ đến địa chỉ cuối cùng của chuỗi thứ nhất txt1.
end2: pointer trỏ đến địa chỉ cuối cùng của chuỗi thứ hai txt2.
l: chiều dài chuỗi con chung dài nhất (nếu tìm thấy) khi lặp đến p và q.

static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  int l;

  *max = 0;
  for (p = (char *) txt1; p < end1; p++) {    // <-- (1)
    for (q = (char *) txt2; q < end2; q++) {  // <-- (2)
      for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++); // <-- (3)
      if (l > *max) {  // <-- (4)
        *max = l;
        *pos1 = p - txt1;
        *pos2 = q - txt2;
      }
    }
  }
}

Lệnh for (1) và (2) để duyệt 2 chuỗi, p trên txt1 và q trên txt2.
Lệnh for (3) tìm chiều dài dãy con chung, tức l.
Lệnh if (4) kiểm tra dãy con chiều dài l có lớn hơn max và cập nhật các giá trị output.

Nếu có 2 dãy con có cùng chiều dài max, thì dãy con nào “nằm trên trái” được chọn. (*)

php_similar_char() hoạt đống giống như similar_text() trong PHP, trả về số dãy con chung có chiều dài lớn nhất.

static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
  int sum = -1;
  int pos1 = -1, pos2 = -1, max = -1;

  php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);  // <-- (1)

  if ((sum = max)) {
    if (pos1 && pos2) {  // <-- (2)
      sum += php_similar_char(txt1, pos1, txt2, pos2);  // <-- (3)
    }
    if ((pos1 + max < len1) && (pos2 + max < len2)) {
      sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max, txt2 + pos2 + max, len2 - pos2 - max);  // <-- (4)
    }
  }

  return sum;
}

Bước 1:
Gọi (1) tới php_similar_str() để tìm chuỗi con chung “nằm bên trái” (từ (*)) dài nhất trong 2 dãy. Nếu có thì cộng vào biến sum ở (3).

(3) thực chất thực hiện giống (1). Khi thực thi (1) trong (3), 1 trong 2 giá trị pos1 hoặc pos2 bằng 0, làm cho lệnh if (2) không thực hiện.

Bước 2:
Cắt chuỗi bằng cách thay đổi pointer và length, và gọi đệ quy (4)

txt1 = txt1 + (pos1 + max)
len1 = len1 - (pos1 + max)
txt2 = txt2 + (pos2 + max)
len2 = len2 - (pos2 + max)

Source code

#include<stdio.h>

static void print_str_index(int len1, int len2) {
  int i, len;
  len = len1 > len2 ? len1 : len2;

  for (i = 0; i < len; i++)
    printf("%d", i%10);
  printf("\n");

  for (i = 0; i < len; i++)
    printf("-");
  printf("\n");
}

static void print_sub_str(const char *txt, int len)
{
  int i;
  for (i = 0; i < len; i++)
    printf("%c", txt[i]);
  printf("\n");
}

/* {{{ php_similar_str
 */
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  int l;

  *max = 0;
  for (p = (char *) txt1; p < end1; p++) {
    for (q = (char *) txt2; q < end2; q++) {
      for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
      if (l > *max) {
        *max = l;
        *pos1 = p - txt1;
        *pos2 = q - txt2;
      }
    }
  }
}
/* }}} */


/* {{{ php_similar_char
 */
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2, int depth)
{
  int sum = -1;
  int pos1 = -1, pos2 = -1, max = -1;

  php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);

  if ((sum = max)) {
    if (pos1 && pos2) {
      printf("[%d-1]:\n", depth);
      print_str_index(len1, len2);
      print_sub_str(txt1, len1);
      print_sub_str(txt2, len2);
      printf("Pos1: %d, Post2: %d, Max: %d, Sum: %d\n", pos1, pos2, max, sum);
      printf("================================\n\n");
      sum += php_similar_char(txt1, pos1, txt2, pos2, depth+1);
    }
    if ((pos1 + max < len1) && (pos2 + max < len2)) {
      printf("[%d-2]:\n", depth);
      print_str_index(len1, len2);
      print_sub_str(txt1, len1);
      print_sub_str(txt2, len2);
      printf("Pos1: %d, Post2: %d, Max: %d, Sum: %d\n", pos1, pos2, max, sum);
      printf("================================\n\n");
      sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max, txt2 + pos2 + max, len2 - pos2 - max, depth+1);
    }
  } else {
    printf("[%d-3]:\n", depth);
    print_str_index(len1, len2);
    print_sub_str(txt1, len1);
    print_sub_str(txt2, len2);
    printf("Pos1: %d, Post2: %d, Max: %d, Sum: %d\n", pos1, pos2, max, sum);
    printf("================================\n\n");
  }

  return sum;
}
/* }}} */
int main(void)
{
    printf("Found %d similar chars\n",
        php_similar_char("PHP IS GREAT", 12, "WITH MYSQL", 10, 1));
    printf("Found %d similar chars\n",
        php_similar_char("WITH MYSQL", 10,"PHP IS GREAT", 12, 1));
    return 0;
}

Tham khảo: https://stackoverflow.com/questions/14136349/how-does-similar-text-work

WyNotMe · April 2, 2019, 2:31pm

Đọc phần lý giải của anh, em cũng mường tượng ra trong đầu (chắc tại vì em còn non xanh quá:weary:) Nhưng lúc trước em có nghĩ đến một cách dễ hiểu hơn nhưng cũng không biết có chuẩn không. Anh thử xem rồi cho em xin thêm ý kiến nhé:
Ta có:

    $str1 = "PHP IS GREAT" được đánh số lần lượt: 0 ứng với P, 1 ứng với H..., 11 ứng với T.
    $str2 = "WITH MYSQL"  cũng được đánh số tương tự.

Giả sử str1 được xếp trước nên sẽ chọn nó làm chuỗi mẫu để đem ra so sánh.

Bước 1: Đặt $count = 0,$len2 = strlen($str2). Sau đó:
So sánh $str1[0] với lần lượt các $str2[$j] (0 <= $j < $len2) => Không thấy trùng khớp => $count không thay đổi ($count = 0), $j vẫn chạy từ 0.
Bước 2 : So sánh $str1[1] với $str2[$j] (0 <= $j < $len2) => Trùng khớp ký tự H ứng với $str2[3]=> $count++. Khi này $j sẽ bắt đầu từ vị trí sau vị trí so khớp được tìm thấy trước đó. Ở đây sẽ bắt đầu từ $str2[4]
Bước 3: So sánh $str1[2] với $str2[$j] (4 <= $j < $len2). Tại đây không thấy so khớp được tìm thấy => $count không thay đổi ($count = 1). Khi này so sánh tiếp theo trên chuỗi $str2 sẽ vẫn bắt đầu từ vị trí thứ 4 dựa theo đánh dấu ban đầu.
Bước 4: So sánh $str1[3] với$str[$j] (4 <= $j < $len2). Tại đây so khớp thấy khoảng trắng space ứng với chuỗistr2[4] =>$count++. Khi này$j sẽ được bắt đầu từ 5 trong lượt so sánh tiếp theo.
Bước 5: So sánh $str1[4] với $str[$j] (5 <= $j < $len2). => Không tìm thấy so khớp vì$j bắt đầu từ 5 mặc dù trong str2 có ký tự I ở vị trí thứ 1 trong chuỗi. => $count không thay đổi, $j vẫn bắt đầu từ 5 trong lượt so sánh tiếp theo.
Bước 6: So sánh $str1[5] với $str[$j] (5 <= $j < $len2). => Tại đây so khớp thấy ký tự S ứng với chuỗi$str2[7] => $count++. Khi này $j sẽ bắt đầu từ 8 trong lượt so khớp tiếp theo.

Tương tự những lượt so khớp tiếp theo sẽ không được tìm thấy =>$count = 3

function similarTextCount($str1, $str2) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        $count = 0;
        $start = 0;
        $j = 0;
        for ($i = 0; $i < $len1; $i++) {
            while ($j < $len2) {
                if ($str1[$i] == $str2[$j]) {
                   $count++;
                    $j++;
                    $start = $j;
                    break;
                } else {
                    $j++;
                }
                if ($j == ($len2 - 1) && $str1[$i] != $str2[$j]) {
                    $j = $start;
                    break;
                } 
            }
        }
        return $count;
    }

hungaya · April 2, 2019, 3:31pm

Có vẻ cách của bạn giống y như implementation của C rồi, đơn giản và hiệu quả hơn.
Giờ mình chỉ viết lại code cho đúng ý diễn dịch bạn thôi.

function similarTextCount($str1, $str2)
{
    $len1 = strlen($str1);
    $len2 = strlen($str2);

    $count = 0;
    $start = 0;

    for ($i = 0; $i < $len1; $i++) {
        for ($j = $start; $j < $len2; $j++) {
            if ($str1[$i] == $str2[$j]) {
                $count++;
                $start = $j + 1;
                break;
            }
        }
    }

    return $count;   
}