search
HomeBackend DevelopmentPHP TutorialPrinciple of PHP function similar_text()_PHP Tutorial

Principle of PHP function similar_text()_PHP Tutorial

Jul 13, 2016 am 10:27 AM
phptextfunctionprinciplestringEvery timeofresemblancecalculate

PHP has a function similar_text() that calculates the similarity of two strings. It can get a percentage to express the similarity of the two strings. The effect is as follows:

similar_text('aaaa', 'aaaa', $percent);

var_dump($percent);

//float(100)

similar_text('aaaa', 'aaaabbbb', $percent);

var_dump($percent);

//float(66.666666666667)

similar_text('abcdef', 'aabcdefg', $percent);

var_dump($percent);

//float(85.714285714286)

Using this function, you can use it to perform fuzzy search functions, or other functions that require fuzzy matching. Recently, I have involved this function in the feature matching step in the research on verification code recognition.

But what kind of algorithm does this function use? I studied its underlying implementation and summarized it in three steps:

(1) Find the longest segment with the same part in the two strings;

(2) Use the same method to find the longest segment with the same parts in the remaining two paragraphs, and so on until there are no more identical parts;

 (3) Similarity = the sum of the lengths of all the same parts * 2 / the sum of the lengths of the two strings;

The source code version I studied is PHP 5.4.6, and the relevant code is located in lines 2951~3031 of the file php-5.4.6/ext/standard/string.c. The following is the source code after I added comments.

//Find the longest segment with the same part in the two strings

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;

//Start traversing based on the first string

 for (p = (char *) txt1; p

//Traverse the second string

 for (q = (char *) txt2; q

// Found that there are the same characters, continue to loop through the search, l is the length of the same part

 for (l = 0; (p + l

//Bubble method to find the longest l and remember the starting position of the same part

 if (l > *max) {

*max = l;

 *pos1 = p - txt1;

 *pos2 = q - txt2;

 }

 }

 }

 }

// Calculate the total length of the same parts of the two strings

static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)

 {

int sum;

 int pos1, pos2, max;

//Find the longest segment of the same part between two strings

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

//Here is the initial assignment to sum and the judgment of the max value

//If max is zero, it means that the two strings do not have any same characters, and if

will jump out

 if ((sum = max)) {

//Recurse for the first half of the segment, and the length of the same segment is accumulated

 if (pos1 && pos2) {

sum += php_similar_char(txt1, pos1,

 txt2, pos2);

 }

//Recurse for the second half of the segment, and the length of the same segment is accumulated

 if ((pos1 + max

sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,

 txt2 + pos2 + max, len2 - pos2 - max);

 }

 }

return sum;

 }

 //PHP function definition

PHP_FUNCTION(similar_text)

 {

Char *t1, *t2;

zval **percent = NULL;

int ac = ZEND_NUM_ARGS();

int sim;

 int t1_len, t2_len;

// Check parameter validity

 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z", &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {

return;

 }

//If there is a third parameter

 if (ac > 2) {

convert_to_double_ex(percent);

 }

//If the length of both strings is 0, return 0

 if (t1_len + t2_len == 0) {

 if (ac > 2) {

 Z_DVAL_PP(percent) = 0;

 }

RETURN_LONG(0);

 }

//Call the above function to calculate the similarity library of two strings

 sim = php_similar_char(t1, t1_len, t2, t2_len);

//You can see the calculation formula of the third parameter percent

 if (ac > 2) {

Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);

 }

RETURN_LONG(sim);

 }

In addition, PHP also provides another function levenshtein() for calculating string similarity. It expresses string similarity by calculating the edit distance of two strings. This is also a very common algorithm. The performance of levenshtein() is better than similar_text(), because from the previous code analysis, we can see that the complexity of similar_text() is O(n^3), n represents the length of the longest string, and levenshtein() The complexity is O(m*n), m and n are the lengths of the two strings respectively.

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/815793.htmlTechArticlePHP has a function similar_text() that calculates the similarity of two strings. It can calculate a percentage to represent the two strings. The degree of similarity between strings. The effect is as follows: similar_text('aaaa', 'aaaa', $...
Statement
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
How can you check if a PHP session has already started?How can you check if a PHP session has already started?Apr 30, 2025 am 12:20 AM

In PHP, you can use session_status() or session_id() to check whether the session has started. 1) Use the session_status() function. If PHP_SESSION_ACTIVE is returned, the session has been started. 2) Use the session_id() function, if a non-empty string is returned, the session has been started. Both methods can effectively check the session state, and choosing which method to use depends on the PHP version and personal preferences.

Describe a scenario where using sessions is essential in a web application.Describe a scenario where using sessions is essential in a web application.Apr 30, 2025 am 12:16 AM

Sessionsarevitalinwebapplications,especiallyfore-commerceplatforms.Theymaintainuserdataacrossrequests,crucialforshoppingcarts,authentication,andpersonalization.InFlask,sessionscanbeimplementedusingsimplecodetomanageuserloginsanddatapersistence.

How can you manage concurrent session access in PHP?How can you manage concurrent session access in PHP?Apr 30, 2025 am 12:11 AM

Managing concurrent session access in PHP can be done by the following methods: 1. Use the database to store session data, 2. Use Redis or Memcached, 3. Implement a session locking strategy. These methods help ensure data consistency and improve concurrency performance.

What are the limitations of using PHP sessions?What are the limitations of using PHP sessions?Apr 30, 2025 am 12:04 AM

PHPsessionshaveseverallimitations:1)Storageconstraintscanleadtoperformanceissues;2)Securityvulnerabilitieslikesessionfixationattacksexist;3)Scalabilityischallengingduetoserver-specificstorage;4)Sessionexpirationmanagementcanbeproblematic;5)Datapersis

Explain how load balancing affects session management and how to address it.Explain how load balancing affects session management and how to address it.Apr 29, 2025 am 12:42 AM

Load balancing affects session management, but can be resolved with session replication, session stickiness, and centralized session storage. 1. Session Replication Copy session data between servers. 2. Session stickiness directs user requests to the same server. 3. Centralized session storage uses independent servers such as Redis to store session data to ensure data sharing.

Explain the concept of session locking.Explain the concept of session locking.Apr 29, 2025 am 12:39 AM

Sessionlockingisatechniqueusedtoensureauser'ssessionremainsexclusivetooneuseratatime.Itiscrucialforpreventingdatacorruptionandsecuritybreachesinmulti-userapplications.Sessionlockingisimplementedusingserver-sidelockingmechanisms,suchasReentrantLockinJ

Are there any alternatives to PHP sessions?Are there any alternatives to PHP sessions?Apr 29, 2025 am 12:36 AM

Alternatives to PHP sessions include Cookies, Token-based Authentication, Database-based Sessions, and Redis/Memcached. 1.Cookies manage sessions by storing data on the client, which is simple but low in security. 2.Token-based Authentication uses tokens to verify users, which is highly secure but requires additional logic. 3.Database-basedSessions stores data in the database, which has good scalability but may affect performance. 4. Redis/Memcached uses distributed cache to improve performance and scalability, but requires additional matching

Define the term 'session hijacking' in the context of PHP.Define the term 'session hijacking' in the context of PHP.Apr 29, 2025 am 12:33 AM

Sessionhijacking refers to an attacker impersonating a user by obtaining the user's sessionID. Prevention methods include: 1) encrypting communication using HTTPS; 2) verifying the source of the sessionID; 3) using a secure sessionID generation algorithm; 4) regularly updating the sessionID.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.