CN112579713B - Address identification method, device, computing equipment and computer storage medium - Google Patents

Abstract

Embodiments of the present invention relate to the field of data processing technology and disclose an address identification method, device, computing device and computer storage medium. The method includes: segmenting the acquired address information to obtain a segmentation result; and determining where the address information is based on the segmentation result. The first transition state in the probabilistic finite state machine; calculate the first probability of the address information in the probabilistic finite state machine according to the first transition state; if the first probability is less than the threshold, determine whether the address information contains typos; if the address information contains For typos, correct the typos and obtain the second transition state of the corrected address information in the probabilistic finite state machine; calculate the second probability of the address information in the probabilistic finite state machine based on the second transition state; if the second probability Greater than or equal to the threshold, the address information is determined to be a valid address. Through the above method, the embodiment of the present invention realizes the recognition of the address information input by the user through the probabilistic finite state machine.

Description

Address identification method, device, computing equipment and computer storage medium

Technical field

Embodiments of the present invention relate to the field of data processing technology, and specifically relate to an address identification method, device, computing device and computer storage medium.

Background technique

Address search is widely used in mobile map application software, map websites, navigation software and other fields. Existing address identification methods mostly use a deterministic finite state machine. The deterministic finite state machine includes multiple state nodes and directed arcs connecting the state nodes. Each directed arc is marked with the distance between the two state nodes. Migration conditions, the structural diagram of the deterministic finite state machine is shown in Figure 1, where S ₀ to S ₃ represent state nodes, I ₀ to I ₆ represent external inputs, and O ₀ to O ₆ represent the state nodes after the interaction with external inputs. The resulting output is used to represent the transition between states. For example, the current state node of the finite state machine is S ₁ . When an external input I ₀ is received, an output O ₀ is generated. This output is used to indicate the state transition to S ₀ .

When using a deterministic finite state machine for address identification, the input address will be considered a valid address only when it completely matches the deterministic finite state machine. That is, if an address can pass through a number of times from the starting state node of the state machine, If an intermediate state node reaches the end state node, the address is considered valid. If the input address contains typos, the address cannot reach the end state node from the start state node, and the input address is considered invalid.

Since addresses in various places do not have unified naming, the address information input by users often contains typos. In this case, when the address is recognized through the deterministic finite state machine, the address will be considered invalid and cannot be recognized.

Contents of the invention

In view of the above problems, embodiments of the present invention provide an address identification method, device, computing device and computer storage medium, which overcome the above problems or at least partially solve the above problems.

According to an aspect of an embodiment of the present invention, an address identification method is provided, which method includes:

Get the address information entered by the user;

Perform word segmentation on the address information to obtain word segmentation results;

Determine the first transition state of the address information in the probabilistic finite state machine according to the word segmentation result;

Calculate the first probability of the address information in the probabilistic finite state machine according to the first transition state;

If the first probability is less than the preset threshold, determine whether the address information contains a typo according to the first migration state;

If the address information contains typos, correct the typos to obtain the second transition state of the corrected address information in the probabilistic finite state machine;

Calculate the second probability of the address information in the probabilistic finite state machine according to the second transition state;

If the second probability is greater than or equal to the preset threshold, it is determined that the address information input by the user is a valid address.

In an optional manner, if the address information contains typos, the typos are corrected to obtain the second transition state of the corrected address information in the probabilistic finite state machine, including:

Determine the text information corresponding to the non-address node contained in the first migration state as the error correction word;

Convert the error-corrected words into pinyin;

Search for error correction word objects that match the pinyin in a preset misspelled word library according to the pinyin;

Use the word with the highest number of searches among the error correction word objects as the error correction comparison object;

Calculate the ratio between the number of searches for the error correction word and the number of searches for the error correction comparison object;

If the proportion is less than the preset proportion, replace the error correction word with the error correction comparison object;

The transition state of the replaced address information in the probabilistic finite state machine is determined as the second transition state.

In an optional manner, if the address information does not contain typos, the method further includes:

Determine the migration sequence of the state nodes;

When the migration sequence is inconsistent with the preset sequence, adjust the migration sequence to be consistent with the preset sequence;

Calculate the third probability of the address information in the probabilistic finite state machine according to the adjusted migration state;

If the third probability is greater than or equal to the preset threshold, it is determined that the address information input by the user is a valid address.

In an optional manner, before obtaining the address information input by the user, the method further includes:

Obtain the address information input by the user historically and obtain training samples;

Extract state nodes of the finite state machine from the training samples;

Determine the migration path of the training sample between the state nodes;

According to the migration path, calculate the migration probability between adjacent state nodes through a hidden Markov model;

The finite state machine containing the transition probability between the state nodes is regarded as a probabilistic finite state machine.

In an optional method, Chinese word segmentation is performed on the address information to obtain word segmentation results, including:

Perform atomic segmentation on the address information to obtain multiple single words;

Merge adjacent words according to different merging methods to obtain the first participle;

The first word segmentation is matched with a preset word association table to obtain a word segmentation result, and all the word segments in the word segmentation result are combined to obtain the address information.

According to another aspect of the embodiment of the present invention, an address identification device is provided, and the device includes:

The acquisition module is used to obtain the address information input by the user;

The word segmentation module is used to segment the address information and obtain the word segmentation results;

A first determination module, configured to determine the first transition state of the address information in the probabilistic finite state machine according to the word segmentation result;

A first calculation module, configured to calculate the first probability of the address information in the probabilistic finite state machine according to the first transition state;

a second determination module, configured to determine whether the address information contains typos according to the first migration state when the first probability is less than a preset threshold;

An error correction module, configured to correct typos when the address information contains typos, and obtain the second transition state of the corrected address information in the probabilistic finite state machine;

A second calculation module, configured to calculate the second probability of the address information in the probabilistic finite state machine according to the second transition state;

A third determination module, configured to determine that the address information input by the user is a valid address when the second probability is greater than or equal to the preset threshold.

According to another aspect of the embodiment of the present invention, a computing device is provided, including: a processor, a memory, a communication interface, and a communication bus. The processor, the memory, and the communication interface complete each other through the communication bus. communication between;

The memory is used to store at least one executable instruction, and the executable instruction causes the processor to perform an operation corresponding to an address identification method.

According to yet another aspect of an embodiment of the present invention, a computer storage medium is provided. At least one executable instruction is stored in the storage medium. The executable instruction causes the processor to perform an operation corresponding to an address identification method.

The embodiment of the present invention obtains the word segmentation result by segmenting the address information input by the user, and determines the migration state of the address information in the probabilistic finite state machine based on the word segmentation result. The probabilistic finite state machine includes state nodes and the migration probability between state nodes. The migration state includes the state node corresponding to the address information and the migration probability between each state node. According to the migration probability corresponding to the migration state, the probability of the address information input by the user in the probabilistic finite state machine is calculated. When the probability is less than the preset threshold When , it means that the address information entered by the user may contain typos, then the typos contained in the address information are corrected, and based on the corrected address information, it is determined whether the address information entered by the user is a valid address. Through the embodiments of the present invention, the identification of address information based on a probabilistic finite state machine is realized, and when the address information input by the user contains typos, the address information can be effectively identified, thereby improving the user experience.

The above description is only an overview of the technical solutions of the embodiments of the present invention. In order to have a clearer understanding of the technical means of the embodiments of the present invention, they can be implemented according to the content of the description, and in order to achieve the above and other purposes, features and The advantages can be more clearly understood, and specific embodiments of the present invention are listed below.

Description of the drawings

Various other advantages and benefits will become apparent to those of ordinary skill in the art upon reading the following detailed description of the preferred embodiments. The drawings are for the purpose of illustrating preferred embodiments only and are not to be construed as limiting the invention. Also throughout the drawings, the same reference characters are used to designate the same components. In the attached picture:

Figure 1 shows a schematic structural diagram of a deterministic finite state machine;

Figure 2 shows a flow chart of an address identification method provided by the first embodiment of the present invention;

Figure 3 shows a schematic structural diagram of a probabilistic finite state machine in an address identification method provided by the first embodiment of the present invention;

Figure 4 shows a flow chart of an address identification method provided by the second embodiment of the present invention;

Figure 5 shows a flow chart of an address identification method according to the third embodiment of the present invention;

Figure 6 shows a functional block diagram of an address identification device according to the fourth embodiment of the present invention;

Figure 7 shows a schematic structural diagram of a computing device in the fifth embodiment of the present invention.

Detailed ways

Exemplary embodiments of the present invention will be described in more detail below with reference to the accompanying drawings. Although exemplary embodiments of the invention are shown in the drawings, it should be understood that the invention may be embodied in various forms and should not be limited to the embodiments set forth herein. Rather, these embodiments are provided to provide a thorough understanding of the invention, and to fully convey the scope of the invention to those skilled in the art.

Application scenarios of embodiments of the present invention include but are not limited to map application software. When the embodiment of the present invention is applied to map application software, the user inputs the address information to be queried in the search box of the map application software. The address information that the user needs to query may be unfamiliar to the user. Therefore, the address information entered by the user may include typos, and the user does not realize that the entered address information contains typos. At this time, if the map application software loads If the address identification method is based on the traditional deterministic finite state machine method, the map application software will prompt the user that the address entered is invalid and the user needs to re-enter the address information, which affects the user experience. Therefore, this application proposes an address identification method that can identify addresses even when the information input by the user contains typos. The following takes the application scenario of map application software as an example to further explain the overall concept of the present application through specific embodiments.

Figure 2 shows a flow chart of an address identification method according to the first embodiment of the present invention. As shown in Figure 2, the method includes the following steps:

Step 110: Obtain the address information input by the user.

In this step, the address information input by the user is the user's Point of Interest (POI). The POI is usually a specific address information, such as a house number address. The user enters the queried address information in the address search box of the map application software and clicks the query button. The map application software first obtains the province and city queried by the user. If the address information entered by the user includes the province and city, it will The address information entered by the user determines the province and city; if the address information entered by the user does not contain province and city information, the parameters related to the address information entered by the user are obtained according to the positioning module in the map application software to determine the province where the user's query information is located. and cities. The parameters related to the address information input by the user include the longitude and latitude of the address information input by the user and the query frequency of the address information, where the longitude and latitude can be obtained through a positioning search engine. Merge the provinces and cities corresponding to the address information input by the user with the address information input by the user to obtain a standard address information. The standard address information is a preset address information. The address information includes Table 1 in order. The address elements in , according to the order from top to bottom in Table 1 below, the levels of the address elements decrease in sequence.

Table 1

Step 120: Perform word segmentation on the address information to obtain word segmentation results.

In this step, when segmenting the address information, if the address information input by the user contains province and city information, segment the address information input by the user directly. If the address information input by the user does not contain province and city information, , then after converting the information input by the user into standard address information, the standard address information is segmented. In one implementation, this step specifically includes the following steps: perform atomic segmentation on the address information to obtain multiple words; merge adjacent words according to different merging methods to obtain the first word segmentation; combine the first word segmentation with the preset The word association table is matched to obtain the word segmentation result, and all the word segments in the word segmentation result are combined to obtain the address information.

Perform atomic segmentation on the address information to obtain multiple words. Among them, atomic segmentation is to segment the address information according to characters to achieve the smallest granularity of word segmentation. For example, "Hunnan District, Shenyang City, Liaoning Province", after atomic segmentation, the results obtained are "Liao" and "Ning" , "province", "shen", "yang", "city", "hun", "nan" and "district" several Chinese characters. Atomic segmentation includes Chinese character segmentation, English character segmentation and number segmentation. When segmenting English characters, there is a pause between adjacent English words, and segmentation is performed based on the pause; when segmenting numbers, a single number is segmented as a character, for example, "Xinlong Street" "No. 6 A Square", when segmented, it will be segmented into several characters such as "新", "龙", "街", "6", "号", "A", and "Square".

When merging adjacent words, they are merged according to the status of each word in the core vocabulary. The core vocabulary stores the status of words and words. This status is used to indicate whether the current word or word can continue to be related to other words. Merge adjacent characters. For example, in the core thesaurus, 1 indicates that a single character can be combined with adjacent characters to form a phrase, 2 indicates that the phrase can still be combined with other characters to form a phrase, and 3 indicates that the phrase cannot be combined with other characters to form a phrase. For example, "Hunnan District, Shenyang City, Liaoning Province", after atomic segmentation, the results obtained are "Liao", "Ning", "province", "Shenyang", "Yang", "city", "Hun", For the Chinese characters "Nan" and "District", when merging, the status identifier of "Liaoning" is 1. It can continue to be merged with "Ning" to obtain "Liaoning" and the status identifier of "Liaoning" in the core thesaurus. is 2, you can continue to merge it with adjacent characters to get "Liaoning Province". The status of this phrase in the core vocabulary is 3, and you can't continue to merge it. Then you will finally get the word "Liaoning Province", and then the word will be determined. is the first participle.

In some embodiments, if the words obtained after atomic segmentation include English words, the adjacent English words are merged and matched with the preset English vocabulary to obtain the first word segmentation. For example, after "Four Seasons Hotel" is segmented, the words obtained are "Four", "Seasons", and "Hotel", and the first participle is "Four Seasons Hotel". In other embodiments, the words obtained after atomic segmentation include multiple numbers, such as "101 Building", and the words obtained after atomic segmentation are "1", "0", "1", and "building", then The first participles obtained are "101" and "building". In some other embodiments, the single characters obtained after atomic segmentation include traditional Chinese characters, and then the traditional Chinese characters are matched with the preset simplified and traditional lexicon before combination, and converted into simplified characters. For example, "张" is converted into "张" ".

In some embodiments, the combined phrase may be an unregistered word in the core lexicon, and the word is selectively added to the core lexicon according to the search frequency of the unregistered word. For example, if the search frequency of a newly built building is higher than a preset value, it means that the unregistered word is frequently searched and belongs to a commonly used address element, so the word will be added to the core thesaurus. Unregistered words may also contain some proper nouns, such as names, abbreviations, etc. In some embodiments, if the proper nouns are not included in the core vocabulary, a related unregistered vocabulary will be preset. These proper nouns are separated for subsequent address identification.

In some embodiments, there are two first word segments that simultaneously contain a certain word in the address information input by the user. The optimal word segmentation combination is determined by matching the first word segmentation with the preset word association table. For example, "goods and services trading center", the first participle obtained may have two different situations. The first includes the following participles: "goods, and, services, trading center", and the second includes the following: For word segmentation "goods, services, services,", the word segmentation result is matched with the preset word association table. The preset word association table includes starting words, terminators, and word frequencies. For example, "service" is in the word association table. A starting word, "service" is a terminator in the word association table, and the word frequency of "service" is relatively high, then the first one is determined as the optimal word segmentation combination, and the first word segmentation combination is used as the word segmentation result. After combining the words in the word segmentation results, the address information input by the user can be obtained.

Step 130: Determine the first transition state of the address information in the probabilistic finite state machine according to the word segmentation result.

In this step, the probabilistic finite state machine includes transition probabilities between state nodes and adjacent state nodes. Figure 3 shows a schematic structural diagram of a probabilistic finite state machine. As shown in Figure 3, the probabilistic finite state machine contains multiple state nodes. The multiple state nodes include gate address category nodes representing the start state and end state. The door address category nodes, intermediate door address category nodes, non-address nodes, and status nodes decrease in order according to the level of the address element. The migration state is matched in the probabilistic state machine according to the word segmentation results. The migration state includes the transition sequence and transition probability between state nodes. For example, the word segmentation results include "Liaoning Province" and "Shenyang City". In the probabilistic finite state machine, the state nodes connected to "Liaoning Province" include "Shenyang City", "Dalian City" and other fourteen state nodes. The probability of interconnection between "Liaoning Province" and these fourteen state nodes is all 1/14, then "Liaoning Province" and "Shenyang City" and the probability 1/14 between them are regarded as part of the first migration state Migration state, all state nodes and the transition probability between state nodes is the first transition state of the address information in the probabilistic finite state machine. For example, when the user's input word is "Taoxian International Airport, No. 1 Airport Road, Taoxian Town, Hunnan District, Shenyang City", the probability state machine matches the migration sequence as "prefecture-level city - district and county - township - road - building unit ”, then the first migration state is expressed as Among them, s ₀ represents the starting state node, q ₀ , q ₁ ... q ₄ represents the intermediate state node, q ₅ represents the ending state node, and x represents the transition probability between adjacent nodes. It should be understood that the first migration state is arranged in the order of the word segmentation results in the address information. Generally speaking, if the address information is input according to the standard address information, the status nodes in the first migration state are arranged in order according to the address element level. Migration is performed in descending order. When the migration state matched by the address information includes the entire path from the start node to the end node, the address information may be a valid address information. The probabilistic finite state machine is trained based on the address information input by the user historically. The specific training process is explained in the following embodiments and will not be described in detail here.

Step 140: Calculate the first probability of the address information in the probabilistic finite state machine according to the transition probability corresponding to the first transition state.

In this step, all transition probabilities in the first transition state are multiplied together to obtain the first probability of the address information in the probabilistic finite state machine. For any address information input by the user, the word segmentation result obtained after word segmentation includes k word segments. The first transition state corresponding to these k word segments in the probabilistic finite state machine is Then the first probability is/> For example, when the user inputs the word "No. 1, Airport Road, Taoxian Town, Hunnan District, Shenyang City", taking the probabilistic finite state machine in Figure 3 as an example, the first transition state is "starting state-prefecture-level city-district" The first probability of "county-township-road-street number" is: 1×0.4×0.2×0.6×1=0.048.

Step 150: When the first probability is less than the preset threshold, determine whether the address information contains typos according to the first migration state.

In this step, the preset threshold is an artificially set value. When the first probability reaches the preset threshold, it can be determined that the address information is a valid address. The state nodes in the probabilistic finite state machine include address nodes and non-address nodes. The address node represents a valid address element, such as "Liaoning Province", "Shenyang City", etc., and the non-address node represents a state node other than a valid address element. For example, "Shenyang City". When the first probability is less than the preset threshold, it may be because the address information contains a typo and the correct address node in the status node cannot be matched according to the typo, causing the first probability to be less than the preset threshold. If the first migration state includes a non-address node, and the migration probabilities of state nodes before the non-address node are all greater than the preset migration probability, it is determined that the address information contains a typo. For example, the preset threshold is 0.03 and the preset migration probability is 0.1. When the user input word is "No. 1, Taoxian International Airport Airport Road, Taoxian Town, Hunnan District, Shenyang City", the state node in the first migration probability is: Starting state - prefecture-level city - district or county - township - non-address node - road - street number. Among them, the probability of any address node transferring to a non-address node is equal. When a non-address node is included, the state transition node is considered to include a non-address node. node and the next address node, the termination node can be reached after the state node is transferred, the first probability calculation result is 1×0.4×0.2×0.02×0.6×1=0.00096, the probability value is far lower than the preset threshold, and there is a non-address in the path node, and the node migration probabilities before and after the non-address node are 1 and 0.4 respectively, both of which are greater than the preset migration probability, so it is determined that the address information contains typos.

When the address information does not contain typos, it is determined that the address information entered by the user is invalid.

Step 160: When the address information contains typos, correct the typos to obtain the second transition state of the corrected address information in the probabilistic finite state machine.

In this step, considering that most of the input methods used by users are Pinyin input methods, the inputted misspelled words are most likely to be homophones. Therefore, the homophones are corrected. Determine the text information corresponding to the non-address node included in the first migration state as the error correction word; convert the error correction word into pinyin; search for the error correction word matching the pinyin in the preset typographical word library according to the pinyin Word object; use the word with the highest number of searches in the error correction word object as the error correction comparison object; calculate the ratio between the number of searches for the error correction word and the number of searches for the error correction comparison object; if the ratio is less than the preset ratio, then The error correction word is replaced with the error correction comparison object; the transition state of the replaced address information in the probabilistic finite state machine is determined as the second transition state. Among them, pinyin and all words corresponding to the pinyin are pre-stored in the misspelled word database. The number of searches for the error correction comparison object is the number of times the word is recorded in the search log, and the number of searches for the error correction word is the number of times the word is recorded in the search log. In some embodiments, the number of searches for the error correction word is determined according to the empirical formula Num*(1+Len/10+IsStr), where Num represents the number of times the error correction word is recorded in the search log, and Len represents the word of the error correction word. Length, IsStr represents the value when the error correction word is Chinese or Pinyin. When the error correction word is Chinese, the value is 0. When the error correction word is Pinyin, the value is 1. For example, when the user inputs the word "No. 1, Airport Road, Taoxian International Airport, Taoxian Town, Hunnan District, Shenyang City", the corrected address information is "No. 1, Airport Road, Taoxian International Airport, Taoxian Town, Hunnan District, Shenyang City" Number".

Step 170: Calculate the second probability of the address information in the probabilistic finite state machine according to the second transition state.

When calculating the second probability based on the second migration state, the second migration state does not contain non-address nodes. For example, when the user inputs the word "No. 1, Taoxian International Airport Airport Road, Taoxian Town, Hunnan District, Shenyang City", the correction The state node in the second migration state after the error is: prefecture-level city + district and county + township + road + street number, and the second probability calculation result is 1×0.4×0.2×0.6×1=0.048.

Step 180: If the second probability is greater than or equal to the preset threshold, determine that the address information input by the user is a valid address.

In this step, if the second probability is less than the preset threshold, it is determined that the address information input by the user is an invalid address.

The embodiment of the present invention obtains the word segmentation result by segmenting the address information input by the user, and determines the migration state of the address information in the probabilistic finite state machine based on the word segmentation result. The probabilistic finite state machine includes state nodes and the migration probability between state nodes. The migration state includes the state node corresponding to the address information and the migration probability between each state node. According to the migration probability corresponding to the migration state, the probability of the address information input by the user in the probabilistic finite state machine is calculated. When the probability is less than the preset threshold When , it means that the address information entered by the user may contain typos, then the typos contained in the address information are corrected, and based on the corrected address information, it is determined whether the address information entered by the user is a valid address. Through the embodiments of the present invention, the identification of address information based on a probabilistic finite state machine is realized, and when the address information input by the user contains typos, the address information can be effectively identified, thereby improving the user experience.

Figure 4 shows a flow chart of an address identification method according to the second embodiment of the present invention. Compared with the first embodiment, the embodiment of the present invention also includes the following steps after step 170. As shown in Figure 4, The method includes the following steps:

Step 210: If the second probability is less than the preset threshold, determine the migration order of the status nodes.

In the embodiment of the present invention, when the address information does not contain typos, but the first migration state can reach the termination node, but the first probability is less than the preset threshold, it may be because the order of the state nodes is incorrect, for example, input The address information is "Taoxian Town, Hunnan District, Shenyang Taoxian International Airport", and the migration order is prefecture-level city-street-district-county-township.

Step 220: When the migration order is inconsistent with the preset order, adjust the migration order to be consistent with the preset order.

In this step, the preset order is the order in which the address elements are arranged from high to low. Taking the address information input in step 210 as "Airport Road, Taoxian Town, Hunnan District, Shenyang Taoxian International Airport" as an example, the adjusted order is "Taoxian International Airport, Taoxian Town, Hunnan District, Shenyang City".

Step 230: Calculate the third probability of the address information in the probabilistic finite state machine according to the adjusted migration state.

In this step, the calculation process of the third probability is the same as the calculation process of step 140. Please refer to the specific description of step 140, which will not be described again here.

Step 240: If the third probability is greater than or equal to the preset threshold, determine that the address information input by the user is a valid address.

In this step, if the third probability is less than the preset threshold, the address information input by the user is an invalid address.

The embodiment of the present invention adjusts the migration order when the order of the address information input by the user is inconsistent with the preset order, so that the address information input by the user can be effectively judged even when the order of the address information input by the user is inconsistent with the preset order. .

Figure 5 shows a flow chart of an address identification method according to the third embodiment of the present invention. Before executing the steps in the first embodiment and the steps in the second embodiment, the embodiment of the present invention further includes the following steps:

Step 310: Obtain the address information input by the user historically and obtain training samples.

In this step, the address information historically input by the user is the address information input by all users when using the map application software, and each piece of address information is used as a training sample.

Step 320: Extract state nodes of the finite state machine from the training samples.

In this step, each training sample is segmented, and the segmentation results are used as status nodes. The word segmentation process is the same as the word segmentation process in step 120 in the first embodiment. Please refer to the description of step 120 in the first embodiment, which will not be described again here.

Step 330: Determine the migration path of the training sample between state nodes.

The migration path includes the migration sequence between state nodes corresponding to each address information.

Step 340: Calculate the migration probability between adjacent state nodes through the hidden Markov model according to the migration path.

Based on the migration paths of all training samples, the migration probability is determined. For example, the training sample contains 60 million address information. Among the 60 million address information, the status node migrated to "Liaoning Province" appears 20 million times. Among these 20 million times, the status node migrated to "Shenyang City" appears 10 million times. times, then the migration probability of "Liaoning Province-Shenyang City" is 0.5.

Step 350: Use a finite state machine containing transition probabilities between state nodes as a probabilistic finite state machine.

According to the migration path, the start status node and the end status node are determined. The start status node includes all status nodes such as provinces, cities, districts and counties, that is, each status node can be used as a start status node. End state nodes include roads, building units, etc. The start state node and the end state node can be the same state node.

The embodiment of the present invention constructs a probabilistic finite state machine based on the address information input by the user in history, so as to facilitate the identification of the address information input by the user based on the constructed finite state machine.

Figure 6 shows a functional block diagram of an address identification device according to the fourth embodiment of the present invention. As shown in Figure 6, the device includes: an acquisition module 410, used to obtain the address information input by the user; a word segmentation module 420, used to segment the address information to obtain a word segmentation result; a first determination module 430, used according to The word segmentation result determines the first transition state of the address information in the probabilistic finite state machine; the first calculation module 440 is used to calculate the first transition state of the address information in the probabilistic finite state machine according to the first transition state. the first probability; the second determination module 450, used to determine whether the address information contains typos according to the first migration state when the first probability is less than the preset threshold; the error correction module 460, used to determine whether the address information contains typos when the first probability is less than the preset threshold; When the address information contains typos, the typos are corrected to obtain the second transition state of the corrected address information in the probabilistic finite state machine; the second calculation module 470 is used to calculate the error according to the second The transition state calculates the second probability of the address information in the probabilistic finite state machine; the third determination module 480 is used to determine the address input by the user when the second probability is greater than or equal to the preset threshold. The information is a valid address.

In an optional manner, the error correction module 460 is further used to:

Determine the text information corresponding to the non-address node contained in the first migration state as the error correction word;

Convert the error-corrected words into pinyin;

Search for error correction word objects that match the pinyin in a preset misspelled word library according to the pinyin;

Use the word with the highest number of searches among the error correction word objects as the error correction comparison object;

Calculate the ratio between the number of searches for the error correction word and the number of searches for the error correction comparison object;

If the proportion is less than the preset proportion, replace the error correction word with the error correction comparison object;

The transition state of the replaced address information in the probabilistic finite state machine is determined as the second transition state.

In an optional manner, the device further includes a fourth determination module 490, configured to determine the migration sequence of the status node when the address information contains a typo; an adjustment module 400, configured to determine the migration sequence of the status node when the address information contains a typo. When the migration sequence is inconsistent with the preset sequence, the migration sequence is adjusted to be consistent with the preset sequence; the third calculation module 401 is used to calculate the probability of the address information being limited according to the adjusted migration state. The third probability in the state machine; the fifth determination module 402 is configured to determine that the address information input by the user is a valid address when the third probability is greater than or equal to the preset threshold.

In an optional manner, the device further includes:

The first acquisition module 403 is used to acquire the address information input by the user historically and obtain training samples;

Extraction module 404, used to extract state nodes of finite state machines from the training samples;

The sixth determination module 405 is used to determine the migration path of the training sample between the state nodes;

The fourth calculation module 406 calculates the migration probability between adjacent state nodes through the hidden Markov model according to the migration path;

The seventh determination module 407 is configured to use the finite state machine containing the transition probability between the state nodes as a probabilistic finite state machine.

In an optional manner, the word segmentation module 420 is further used to:

Perform atomic segmentation on the address information to obtain multiple single words;

Merge adjacent words according to different merging methods to obtain the first participle;

The first word segmentation is matched with a preset word association table to obtain a word segmentation result, and all the word segments in the word segmentation result are combined to obtain the address information.

In the embodiment of the present invention, the address information input by the user is segmented into words through the word segmentation module 420 to obtain the word segmentation result. The first determination module 430 determines the migration state of the address information in the probabilistic finite state machine according to the word segmentation result. The probabilistic finite state machine includes state nodes and Migration probability between state nodes. The migration state includes the state node corresponding to the address information and the migration probability between each state node. According to the migration probability corresponding to the migration state, the probability of the address information input by the user in the probabilistic finite state machine is calculated. , when the probability is less than the preset threshold, it means that the address information input by the user may contain typos, then the typos contained in the address information are corrected through the error correction module 460, and the address information input by the user is determined based on the corrected address information. Whether the address information is a valid address. Through the embodiments of the present invention, address information can be identified based on a probabilistic finite state machine, and when the address information input by the user contains typos, the address information can be effectively identified, thereby improving the user experience.

Embodiments of the present invention provide a non-volatile computer storage medium that stores at least one executable instruction. The computer executable instruction can execute the address identification method in any of the above method embodiments.

Figure 7 shows a schematic structural diagram of a computing device in the fifth embodiment of the present invention. The specific embodiment of the present invention does not limit the specific implementation of the computing device.

As shown in FIG. 7 , the computing device may include: a processor 502 , a communications interface 504 , a memory 506 , and a communications bus 508 .

Among them: the processor 502, the communication interface 504, and the memory 506 complete communication with each other through the communication bus 408. The communication interface 504 is used to communicate with network elements of other devices such as clients or other servers. The processor 502 is configured to execute the program 510. Specifically, it can execute the relevant steps in the above embodiment of the address identification method.

Specifically, program 510 may include program code including computer operating instructions.

The processor 502 may be a central processing unit (CPU), an application specific integrated circuit (ASIC), or one or more integrated circuits configured to implement embodiments of the present invention. The one or more processors included in the computing device may be the same type of processor, such as one or more CPUs; or they may be different types of processors, such as one or more CPUs and one or more ASICs.

Memory 506 is used to store programs 510. The memory 506 may include high-speed RAM memory, and may also include non-volatile memory (non-volatile memory), such as at least one disk memory.

The program 510 can be specifically used to cause the processor 502 to execute steps 110 to 180 in Figure 2, steps 210 to 240 in Figure 4, steps 310 to 350 in Figure 5, and implement modules 410 to 6 in Figure 6 Functions in module 407.

The algorithms or displays provided herein are not inherently associated with any particular computer, virtual system, or other device. Various general-purpose systems can also be used with teaching based on this. From the above description, the structure required to construct such a system is obvious. Furthermore, embodiments of the present invention are not directed to any specific programming language. It should be understood that a variety of programming languages may be utilized to implement the invention described herein, and that the above descriptions of specific languages are intended to disclose the best mode of carrying out the invention.

In the instructions provided here, a number of specific details are described. However, it is understood that embodiments of the invention may be practiced without these specific details. In some instances, well-known methods, structures, and techniques have not been shown in detail so as not to obscure the understanding of this description.

Similarly, it will be understood that in the above description of exemplary embodiments of the invention, various features of embodiments of the invention are sometimes grouped together into a single implementation in order to streamline the invention and assist in understanding one or more of the various inventive aspects. examples, diagrams, or descriptions thereof. This method of disclosure, however, is not to be interpreted as reflecting an intention that the claimed invention requires more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive aspects lie in less than all features of a single foregoing disclosed embodiment. Thus, the claims following the Detailed Description are hereby expressly incorporated into this Detailed Description, with each claim standing on its own as a separate embodiment of this invention.

Those skilled in the art will understand that modules in the devices in the embodiment can be adaptively changed and arranged in one or more devices different from that in the embodiment. The modules or units or components in the embodiments may be combined into one module or unit or component, and furthermore they may be divided into a plurality of sub-modules or sub-units or sub-components. All features disclosed in this specification (including accompanying claims, abstract and drawings) and any method so disclosed may be employed in any combination, except that at least some of such features and/or processes or units are mutually exclusive. All processes or units of the equipment are combined. Each feature disclosed in this specification (including accompanying claims, abstract and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise.

Furthermore, those skilled in the art will understand that although some embodiments herein include certain features included in other embodiments but not others, combinations of features of different embodiments are meant to be within the scope of the invention. and form different embodiments. For example, in the following claims, any of the claimed embodiments may be used in any combination. It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word "comprising" does not exclude the presence of elements or steps not listed in a claim. The word "a" or "an" preceding an element does not exclude the presence of a plurality of such elements. The invention may be implemented by means of hardware comprising several different elements and by means of a suitably programmed computer. In the element claim enumerating several means, several of these means may be embodied by the same item of hardware. The use of the words first, second, third, etc. does not indicate any order. These words can be interpreted as names. Unless otherwise specified, the steps in the above embodiments should not be understood as limiting the order of execution.

Claims (9)

1. An address identification method, the method comprising:

acquiring address information input by a user;

performing word segmentation on the address information to obtain a word segmentation result;

determining a first migration state of the address information in a probability finite state machine according to the word segmentation result, wherein the probability finite state machine comprises a state node and migration probability between the state nodes; the state node comprises an address node and a non-address node;

calculating a first probability of the address information in the probability finite state machine according to the migration probability corresponding to the first migration state;

if the first probability is smaller than a preset threshold, determining whether the address information contains wrongly written characters according to the first migration state includes: if the first probability is smaller than the preset threshold value, determining the migration probability between the state node and the state node contained in the first migration state; if the state nodes contained in the first migration state comprise non-address nodes, determining a first migration probability of the state nodes before the non-address nodes and a second migration probability of the state nodes after the non-address nodes; if the first migration probability and the second migration probability are both larger than the preset migration probability, determining that the address information contains wrongly written words;

If the address information contains wrongly written words, correcting the wrongly written words to obtain a second migration state of the corrected address information in the probability finite state machine;

calculating a second probability of the address information in the probability finite state machine according to the second migration state;

and if the second probability is greater than or equal to the preset threshold value, determining that the address information input by the user is an effective address.

2. The method of claim 1, wherein if the address information includes a wrongly written word, correcting the wrongly written word to obtain a second migration state of the corrected address information in the probabilistic finite state machine, comprising:

determining text information corresponding to the non-address node contained in the first migration state as an error correction word;

converting the error correction words into pinyin;

searching an error correction word object matched with the pinyin in a preset wrongly written word library according to the pinyin;

taking the word with the highest searching frequency in the error correction word object as an error correction comparison object;

calculating the proportion between the searching times of the error correction words and the searching times of the error correction comparison objects;

If the specific gravity is smaller than the preset specific gravity, replacing the error correction word with the error correction comparison object;

and determining the migration state of the replaced address information in the probability finite state machine as the second migration state.

3. The method of claim 1, wherein if the address information does not contain misplaced words, the method further comprises:

determining the migration sequence of the state nodes;

when the migration sequence is inconsistent with a preset sequence, the migration sequence is adjusted to be consistent with the preset sequence;

calculating a third probability of the address information in the probability finite state machine according to the adjusted migration state;

and if the third probability is greater than or equal to the preset threshold value, determining that the address information input by the user is an effective address.

4. The method of claim 1, wherein prior to obtaining the address information entered by the user, the method further comprises:

acquiring address information input by a user in a history way to obtain a training sample;

extracting state nodes of a finite state machine from the training samples;

determining a migration path of the training sample between the state nodes;

Calculating migration probability between adjacent state nodes through a hidden Markov model according to the migration path;

and taking a finite state machine containing migration probability among the state nodes as a probability finite state machine.

5. The method of claim 1, wherein performing chinese word segmentation on the address information to obtain a word segmentation result comprises:

performing atomic segmentation on the address information to obtain a plurality of single words;

combining adjacent single words according to different combining modes to obtain a first word segmentation;

and matching the first word segmentation with a preset word association table to obtain a word segmentation result.

6. The method of claim 1, wherein after obtaining the first segmentation, the method further comprises:

if the first word segmentation contains the unregistered word, taking the unregistered word as a word segmentation result under the condition that the search frequency of the unregistered word is greater than a preset value.

7. An address identifying apparatus, the apparatus comprising:

the acquisition module is used for acquiring address information input by a user;

the word segmentation module is used for segmenting the address information to obtain a word segmentation result;

the first determining module is used for determining a first migration state of the address information in a probability finite state machine according to the word segmentation result; the probability finite state machine comprises a state node and a transition probability between the state nodes; the state node comprises an address node and a non-address node;

The first calculation module is used for calculating a first probability of the address information in the probability finite state machine according to the first migration state; the state node comprises an address node and a non-address node;

the second determining module is configured to determine, according to the first migration state, whether the address information includes a wrongly written word when the first probability is smaller than a preset threshold, where the second determining module includes: if the first probability is smaller than the preset threshold value, determining the migration probability between the state node and the state node contained in the first migration state; if the state nodes contained in the first migration state comprise non-address nodes, determining a first migration probability of the state nodes before the non-address nodes and a second migration probability of the state nodes after the non-address nodes; if the first migration probability and the second migration probability are both larger than the preset migration probability, determining that the address information contains wrongly written words;

the error correction module is used for correcting the wrongly written words when the address information contains wrongly written words, and obtaining a second migration state of the address information after error correction in the probability finite state machine;

A second calculation module, configured to calculate a second probability of the address information in the probability finite state machine according to the second migration state;

and the third determining module is used for determining that the address information input by the user is an effective address when the second probability is greater than or equal to the preset threshold value.

8. A computing device, comprising: the device comprises a processor, a memory, a communication interface and a communication bus, wherein the processor, the memory and the communication interface complete communication with each other through the communication bus;

the memory is configured to store at least one executable instruction, where the executable instruction causes the processor to perform operations corresponding to an address identification method according to any one of claims 1 to 6.

9. A computer storage medium having stored therein at least one executable instruction for causing a processor to perform operations corresponding to an address identification method according to any one of claims 1 to 6.