CN118760796A - Address location method and device - Google Patents

Abstract

The embodiments of the present disclosure disclose an address location method and device. The specific implementation of the method includes: slicing the address text by sliding window to obtain a word unit set; matching the word unit set with the hierarchical node data in the geographic hierarchical tree to obtain matching hierarchical nodes, wherein the hierarchical node data includes: a word unit set obtained by slicing the hierarchical node name by sliding window; for each matching hierarchical node, calculating the score value of the hierarchical node according to the weight of the matching word unit; obtaining all candidate address links containing matching hierarchical nodes through depth-first traversal; calculating the score of each candidate address link according to the score value of the hierarchical node contained in the candidate address link, and selecting the candidate address link with the highest score as the location result. This implementation can realize a fast and accurate address location function, and has a wide range of application value.

Description

Address location method and device

Technical Field

Embodiments of the present disclosure relate to the field of computer technology, and in particular to an address location method and device.

Background Art

Address location is the process of mapping the address text described in natural language to a standard geographic hierarchy. The geographic hierarchy is a hierarchical structure divided according to the spatial scope. Generally, different geographic hierarchies can be divided according to the actual usage scenarios, such as the geographic hierarchy of security patrols, the geographic hierarchy of logistics distribution, etc.

Different from the common address query (mapping address text to longitude and latitude coordinates), address location maps the address text entered by the user to a predefined geographic hierarchy. In government service scenarios, address location is very common. In these application scenarios, the address text involved mainly comes from manual filling by individual users and managers, and there are often conflicts in geographic hierarchy, irregular writing, incomplete addresses, typos, etc., which poses a huge challenge to address location.

The existing full-text search method for address location relies on text similarity calculation, but the free matching between texts cannot adapt to the natural hierarchical structure of the address. The rule matching method based on hierarchical selection in the existing technology is limited to a certain extent by the formulation of rules. Its pre-defined rule system cannot adapt well to the complex and diverse address filling situations of users, and may fail to match the results that users really want because the administrative levels filled in by users are not standard or conflicting.

Summary of the invention

The embodiments of the present disclosure provide an address location method and device.

In a first aspect, an embodiment of the present disclosure provides an address placement method, comprising: slicing an address text through a sliding window to obtain a word set; matching the word set with hierarchical node data in a geographic hierarchical tree to obtain matching hierarchical nodes, wherein the hierarchical node data comprises: a word set obtained by slicing the hierarchical node name through a sliding window; for each matching hierarchical node, calculating a score value of the hierarchical node according to a weight of the matching word; obtaining all candidate address links containing matching hierarchical nodes through a depth-first traversal; calculating a score for each candidate address link according to the score values of the hierarchical nodes contained in the candidate address link, and selecting the candidate address link with the highest score as the placement result.

In some embodiments, matching the word set with the hierarchical node data in the geographic hierarchical tree to obtain matching hierarchical nodes includes: querying a pre-built inverted index for each word in the word set to obtain all hierarchical nodes containing the word, thereby obtaining matching hierarchical nodes.

In some embodiments, the method further includes: for each hierarchical node in the geographic hierarchical tree, performing sliding window slicing on the node name to obtain a corresponding fuzzy word set; for each fuzzy word in the fuzzy word set, registering all hierarchical nodes containing the fuzzy word into the inverted index of the word.

In some embodiments, the method further comprises: calculating the weight of a word-gram according to the frequency of occurrence of each word-gram in the word-gram set in the hierarchical node data in the geographical hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight.

In some embodiments, the step of calculating the score value of the level node according to the weight of the matched word-gram includes: calculating the score value of the level node according to the word-gram weight, the word-gram length, and the matching ratio of the level node.

In some embodiments, the score of each candidate address link is calculated based on the score values of the hierarchical nodes included in the candidate address link, including: for each hierarchical node included in the candidate address link, weighting the score value of the hierarchical node by the hierarchical weight; and accumulating the weighted values of the score values of all hierarchical nodes included in the candidate address link as the score of the candidate address link.

In some embodiments, before calculating the score value of the hierarchical node according to the weight of the matching word, the method also includes: querying the weight of the matching word through a pre-generated word weight index; wherein the word weight index is generated by the following steps: for each hierarchical node in the geographic hierarchical tree, sliding window slicing the node name to obtain a corresponding fuzzy word set; calculating the weight of the fuzzy word according to the frequency of occurrence of each fuzzy word in the fuzzy word set in the hierarchical node data in the geographic hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight; storing the weight of each fuzzy word in a key-value type data structure to generate a word weight index.

In a second aspect, an embodiment of the present disclosure provides an address placement device, comprising: a word segmentation unit, configured to perform sliding window slicing on an address text to obtain a word set; a matching unit, configured to match the word set with hierarchical node data in a geographic hierarchical tree to obtain matched hierarchical nodes, wherein the hierarchical node data comprises: a word set obtained by performing sliding window slicing on the hierarchical node name; a calculation unit, configured to calculate, for each matched hierarchical node, a score value of the hierarchical node according to the weight of the matched word; a link unit, configured to obtain all candidate address links containing matched hierarchical nodes through a depth-first traversal; a selection unit, configured to calculate the score of each candidate address link according to the score values of the hierarchical nodes contained in the candidate address link, and select the candidate address link with the highest score as the placement result.

In some embodiments, the matching unit is further configured to: query a pre-constructed inverted index for each word in the word set to obtain all hierarchical nodes containing the word, and obtain matching hierarchical nodes.

In some embodiments, the device also includes an inverted index unit, which is configured to: for each hierarchical node in the geographic hierarchical tree, perform sliding window slicing on the node name to obtain a corresponding fuzzy word element set; for each fuzzy word element in the fuzzy word element set, register all hierarchical nodes containing the fuzzy word element into the inverted index of the word element.

In some embodiments, the device also includes a weight calculation unit configured to calculate the weight of the word based on the frequency of each word in the word set appearing in the hierarchical node data in the geographic hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight.

In some embodiments, the calculation unit is further configured to: calculate the score value of the level node according to the word unit weight, word unit length, and matching ratio of the level node.

In some embodiments, the link unit is further configured to: for each hierarchical node included in the candidate address link, weight the score value of the hierarchical node by the hierarchical weight; and accumulate the weighted values of the score values of all hierarchical nodes included in the candidate address link as the score of the candidate address link.

In some embodiments, the device also includes a weight index unit, which is configured to: before calculating the score value of the hierarchical node based on the weight of the matching word, query the weight of the matching word through a pre-generated word weight index; wherein the word weight index is generated through the following steps: for each hierarchical node in the geographic hierarchical tree, the node name is sliced by sliding window to obtain the corresponding fuzzy word set; the weight of the fuzzy word is calculated according to the frequency of occurrence of each fuzzy word in the fuzzy word set in the hierarchical node data in the geographic hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight; the weight of each fuzzy word is stored in a key-value type data structure to generate a word weight index.

In a third aspect, an embodiment of the present disclosure provides an electronic device, comprising: one or more processors; a storage device on which one or more computer programs are stored, and when the one or more computer programs are executed by the one or more processors, the one or more processors implement a method as described in any one of the first aspects.

In a fourth aspect, an embodiment of the present disclosure provides a computer-readable medium having a computer program stored thereon, wherein the computer program, when executed by a processor, implements the method as described in any one of the first aspects.

The address location method and device provided by the embodiments of the present disclosure address the technical problems of result similarity measurement and text fuzzy matching in address location, integrate geographic hierarchy, database index and text retrieval technology, and propose a new address location method based on hierarchical structure. The present disclosure adopts a hierarchical storage structure for standard geographic hierarchy data, establishes an inverted index based on the hierarchical storage structure, and designs a location matching method in combination with the hierarchical characteristics of the address, and obtains the optimal location result by matching the score of the address link. The present disclosure can be effectively applied to government service scenarios such as questionnaire surveys and event dispatching to achieve fast and accurate address location functions, and has wide application value.

It should be understood that the content described in this section is not intended to identify the key or important features of the embodiments of the present disclosure, nor is it intended to limit the scope of the present disclosure. Other features of the present disclosure will become easily understood through the following description.

BRIEF DESCRIPTION OF THE DRAWINGS

Other features, objects and advantages of the present disclosure will become more apparent from the detailed description of non-limiting embodiments made with reference to the following drawings:

FIG1 is an exemplary system architecture diagram in which an embodiment of the present disclosure may be applied;

FIG2 is a flow chart of an embodiment of an address location method according to the present disclosure;

FIG3 is a flow chart of another embodiment of an address location method according to the present disclosure;

4a-4e are schematic diagrams of application scenarios of the address placement method according to the present disclosure;

FIG5 is a schematic structural diagram of an address placement device according to an embodiment of the present disclosure;

FIG. 6 is a schematic diagram of a computer system of an electronic device suitable for implementing an embodiment of the present disclosure.

DETAILED DESCRIPTION

The present disclosure is further described in detail below in conjunction with the accompanying drawings and embodiments. It is understood that the specific embodiments described herein are only used to explain the relevant invention, rather than to limit the invention. It is also necessary to explain that, for ease of description, only the parts related to the relevant invention are shown in the accompanying drawings.

It should be noted that, in the absence of conflict, the embodiments and features in the embodiments of the present disclosure may be combined with each other. The present disclosure will be described in detail below with reference to the accompanying drawings and in combination with the embodiments.

FIG. 1 shows an exemplary system architecture 100 to which an embodiment of an address location method or an address location apparatus of the present disclosure may be applied.

As shown in Fig. 1, system architecture 100 may include terminal devices 101, 102, 103, network 104 and server 105. Network 104 is used to provide a medium for communication links between terminal devices 101, 102, 103 and server 105. Network 104 may include various connection types, such as wired, wireless communication links or optical fiber cables, etc.

Users can use terminal devices 101, 102, 103 to interact with server 105 through network 104 to receive or send messages, etc. Various communication client applications can be installed on terminal devices 101, 102, 103, such as 3D video players, web browser applications, shopping applications, search applications, instant messaging tools, email clients, social platform software, etc.

Terminal devices 101, 102, 103 can be hardware or software. When terminal devices 101, 102, 103 are hardware, they can be various electronic devices with display screens and supporting 3D video playback, including but not limited to smart phones, tablet computers, e-book readers, MP3 players (Moving Picture Experts Group Audio Layer III, Moving Picture Experts Group Audio Layer 3), MP4 (Moving Picture Experts Group Audio Layer IV, Moving Picture Experts Group Audio Layer 4) players, laptop computers and desktop computers, etc. When terminal devices 101, 102, 103 are software, they can be installed in the electronic devices listed above. It can be implemented as multiple software or software modules (for example, to provide distributed services), or it can be implemented as a single software or software module. No specific limitation is made here.

The server 105 may be a server that provides various services, such as processing the address text sent by the terminal device, mapping it to standard geographical hierarchy nodes, obtaining the location result and then feeding it back to the terminal device.

It should be noted that the server can be hardware or software. When the server is hardware, it can be implemented as a distributed server cluster consisting of multiple servers, or it can be implemented as a single server. When the server is software, it can be implemented as multiple software or software modules (for example, multiple software or software modules used to provide distributed services), or it can be implemented as a single software or software module. No specific limitation is made here. The server can also be a server of a distributed system, or a server combined with a blockchain. The server can also be a cloud server, or an intelligent cloud computing server or intelligent cloud host with artificial intelligence technology.

It should be noted that the address location method provided in the embodiments of the present disclosure is generally executed by the server 105 , and accordingly, the address location device is generally disposed in the server 105 .

It should be understood that the number of terminal devices, networks and servers in Figure 1 is only illustrative. Any number of terminal devices, networks and servers may be provided according to implementation requirements.

The following is an explanation of the nouns involved in this article:

1. Geographical hierarchy tree: As shown in Figure 4b, a geographical hierarchy based on administrative divisions is essentially a tree structure that describes hierarchical relationships. It can be formally represented as T<V,E,root>, where V = {node ₁ ,…,node _n } represents the set of tree nodes (also called hierarchical nodes), E = {edge ₁ ,…,edge _h } represents the set of edges, and root represents the root node of the entire tree. Each tree node represents a region/location, which is the target object of address location matching; the edge represents the parent-child relationship between nodes, representing the affiliation between regions/locations. Generally, regions refer to administrative divisions (such as provinces, cities, districts, streets, towns, communities, etc.), and places refer to points of interest (POI). The lowest level of a residential location is the community, and the lowest level of other POIs (such as hospitals, schools, shopping malls, etc.) is the street, which can also be affiliated to a district or city.

2. Hierarchical node node: represents a region/place in the geographic hierarchical tree tree, corresponding to a node in Figure 4b. Hierarchical nodes have three basic attributes: parent node parent, name name, and level level. Parent is the parent node of the current node, which is used to maintain the tree-shaped hierarchical structure and form address links; name is the name of the hierarchical node, that is, the name of the region/place; level is an integer from 1 to 9, indicating the level of the hierarchical node, and the correspondence with the geographical level is shown in Table 1. In practical applications, all regions/places can be represented in the form of hierarchical nodes, and thus form a standard geographic hierarchical tree. The root node root of each geographic hierarchical tree represents the current province, that is, root.level=1.

level Geographic level 1 Province 2 city 3 district 4 Street/Town 5 Community/Village 6 Points of Interest 7 Building 8 unit 9 household

Table 1 Hierarchical node levels and their meanings

3. Address link link: Based on the geographic hierarchical tree, given a hierarchical node node, the node sequence formed by the root node root to node is an address link link. For example, in Figure 4b, given a hierarchical node node ₁₃ , the corresponding address link is link = <root, node ₁ , node ₄ , node ₆ , node ₁₀ , node ₁₃ >, and extracting the name attribute of each hierarchical node in the address link will obtain the text representation of the address link, that is, [province]-[city 1]-[district 2]-[street 1]-[community 2]-[suburb 2]. The hierarchical node with the largest level value in the address link is called the terminal node of the link, and the terminal node of the above address link is node _13. This article uses the lowercase letter l to represent an address link.

4. Address text query: an address text described in natural language, which contains some administrative division related information, such as "Building 1, Tongtai International Residence, Economic Development Zone, Beijing". This article uses lowercase letter q to represent an address text.

5. Word: Perform n-gram sliding window slicing on the text to obtain a word sequence, with a sliding window size of n∈[2,maxSize], where maxSize is the maximum window size. Considering the naming rules of places (place names usually do not exceed 8 characters), maxSize is generally set to 8. For example, perform 2-gram sliding window slicing on the text "Tongtai International Mansion" to obtain a word sequence of W _2-gram = {"Tongtai", "Thailand", "International", "International", "Mansion"}, perform 3-gram sliding window slicing to obtain a word sequence of W _3-gram = {"Tongtai", "Thailand International", "International", "Mansion"}, and merge all n-gram word sequences to obtain the fuzzy word set corresponding to the text This article uses lowercase letter w to represent a word unit, and uppercase letter W to represent the set of all word units obtained by performing n-gram sliding window slicing on a text.

Before executing the address placement method, the data index initialization process shown in FIG. 4c may be performed first:

Data index initialization includes two steps: building an inverted index and calculating word weights. The word inverted index and word weight index are generated respectively. The word inverted index is used to quickly query the hierarchical nodes of word matching, and the word weight index is used to quickly query the weight value of the importance of the word in the current geographic level data.

(a) Building an inverted index

Inverted index is a common technical solution in search engines, which can speed up the efficiency of data query. In the address placement method, the inverted index technology can be used to quickly locate the hierarchical nodes corresponding to the query word. The inverted index Index(·) is stored in a key-value type data structure, where the key is the word and the value is a list of hierarchical nodes containing the word. After the inverted index is built, the corresponding value value _i can be quickly queried through the key key _i , that is, value _i = Index(key _i ). In the inverted index, the set of all word elements is the set of all keys, that is, Index.Keys = {w ₁ ,…,w _N }, and the total number of word elements in the inverted index is recorded as N.

The construction process is as follows: first input the geographical hierarchical tree T<V,E,root>, where V = {node ₁ ,…,node _i ,…,node _n }, node _i represents a hierarchical node with three basic attributes, namely node _i = (parent, name, level). For each hierarchical node node _i , perform n-gram sliding window slicing on the node name node _i .name to obtain the corresponding fuzzy word set k _i is the total number of fuzzy word units corresponding to the text. For each word unit w _j , the current node node _i is registered in the inverted index of the word unit w _j , that is, Index(w _j ) = Index(w _j )∪{node _i }, until all hierarchical nodes are traversed. After the inverted index structure Index(·) is constructed, the list Index(w _j ) of all hierarchical nodes containing the word unit can be quickly obtained by querying the word unit w _j. The number of hierarchical nodes in Index(w _j ) can be written as Index(w _j ).size. At the same time, the set of all word units in the inverted index is obtained, Index.Keys = {w ₁ ,…,w _N }, where N is the total number of word units in the inverted index.

(b) Constructing weight index

The weight index is a data structure that stores the weight value of each word, and is used to quickly query the weight value of the importance of the word in the current geographic level data to avoid repeated calculations. The weight index is also stored in a key-value type data structure, where the key is the word and the value is the weight value of the word. After the weight index is constructed, the corresponding value value _i can be quickly queried through the key key _i , that is, value _i =Weight(key _i ). The specific calculation method of the weight can be obtained through step 203.

As shown in Figure 4d, the address placement method mainly includes three processes: matching hierarchical nodes, searching candidate links, and selecting the optimal link. Among them, matching hierarchical nodes obtains the query word set by sliding window slicing the query address text, quickly matches hierarchical nodes according to the inverted index, and calculates the matching score of hierarchical nodes according to word weights and node information; searching candidate links is based on the tree structure of geographic hierarchical data, and all candidate address links containing matching nodes are searched through depth-first traversal; selecting the optimal link For all candidate links, the score of each address link is calculated according to the matching score of the hierarchical node, and the candidate address link with the highest score is returned as the final query placement result.

2, a process 200 of an embodiment of an address location method according to the present disclosure is shown. The address location method comprises the following steps:

Step 201, performing sliding window slicing on the address text to obtain a word unit set.

In this embodiment, the execution subject of the address location method (such as the server shown in FIG1 ) can receive the address text input by the user through the terminal device through a wired connection or a wireless connection. For the address text q input by the user, n-gram sliding window slicing is performed to obtain all possible query word element sets W = {w ₁ ,…,w _j ,…,w _k }, where w _j is a query word element.

The text is sliced by n-gram window to obtain a word sequence, and the sliding window size n∈[2,maxSize], maxSize is the maximum window size. Considering the naming rules of places (place names usually do not exceed 8 characters), maxSize is generally set to 8. For example, for the text of "Tongtai International Mansion", 2-gram window slicing is performed to obtain the word sequence of W _2-gram = {"Tongtai", "Thailand", "International", "International", "Mansion"}, and 3-gram window slicing is performed to obtain the word sequence of W _3-gram = {"Tongtai", "Thailand International", "International", "Mansion"}. All n-gram word sequences are merged to obtain the fuzzy word set corresponding to the text. This article uses lowercase letter w to represent a word unit, and uppercase letter W to represent the set of all word units obtained by n-gram window slicing of a text.

Step 202 : Match the word set with the hierarchical node data in the geographical hierarchical tree to obtain matching hierarchical nodes.

In this embodiment, the hierarchical node data includes: a word-unit set obtained by sliding window slicing the hierarchical node name.

For a single word _wj, traverse all the hierarchical node data V = {node ₁ , ..., node _i , ..., node _n } in turn and determine whether it meets the conditions If it matches, the node is added to the matching node set M. The time complexity of the whole process is O(n).

Step 203: For each matched level node, a score value of the level node is calculated according to the weight of the matched word.

In this embodiment, the weight of each word can be calculated in advance based on the frequency of occurrence of all words in the hierarchical node data. The higher the frequency of occurrence, the smaller the weight. For example, the TF-IDF (term frequency-inverse document frequency) of each word is calculated as the weight of the word.

Each level node corresponds to multiple word units. For each level node, the score value of a level node can be calculated through the weight of each word unit in the level node data, and finally the highest score value among the scores of the level nodes calculated from multiple word units is taken as the score value of the level node.

The weight value of the word unit can be used as the score value of the hierarchical node. The weight value of the word unit can also be weighted and modified according to the length of the word unit and used as the score value of the hierarchical node.

In some optional implementations of the present embodiment, the weight of a matching word is queried through a pre-generated word weight index; wherein the word weight index is generated through the following steps: for each hierarchical node in the geographic hierarchical tree, the node name is sliced by sliding window to obtain a corresponding fuzzy word set; the weight of the fuzzy word is calculated based on the frequency of occurrence of each fuzzy word in the hierarchical node data in the geographic hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight; the weight of each fuzzy word is stored in a key-value type data structure to generate a word weight index.

The word weight index is a data structure that stores the weight value of each word. It is used to quickly query the weight value of the importance of the word in the current geographic level data to avoid repeated calculations. The weight index is also stored in a key-value type data structure, where the key is the word and the value is the weight value of the word. After the weight index is built, the corresponding value value _i can be quickly queried through the key key _i , that is, value _i = Weight(key _i ).

The definition of each word unit weight is as follows:

The total number of words is N, and the number of occurrences of word _wi in the geographic level data is n. The importance (weight) of word _wi can be defined as:

Where Norm(·) is a batch normalization operation, and the maximum-minimum normalization is used here.

In some optional implementations of this embodiment, the step of calculating the score value of the level node based on the weight of the matching word-gram includes: calculating the score value of the level node based on the word-gram weight, word-gram length, and matching ratio of the level node.

Defines the calculation method of the matching score NodeScore of the level node. Given an address text q and a level node node _i , the score value of the level node is:

Where _Wq is the word set of the n-gram sliding window slice of the address text q, _wj is a query word in _Wq ; Weight( _wj ) represents the importance of word _wj in the geographic hierarchy tree, and its definition is shown in formula (1); lenght(·) represents the number of characters counted, lenght( _wj ) represents the number of characters of word _wj (indicating the word length), and length( _nodei.name ) represents the number of characters in the node name of the hierarchical node node _i . Indicates the matching ratio of level nodes.

Step 204: Obtain all candidate address links containing matching hierarchical nodes through depth-first traversal.

In this embodiment, by matching the hierarchical node set M of the query content, a depth-first traversal is performed in the geographic hierarchical tree T<V, E, root> to search for the terminal nodes of all candidate address links.

For example, in Figure 4e, assume that all dark nodes are hierarchical nodes that match the query content, and the set of these nodes is denoted as M.

That is, M = {root, node ₄ , node ₅ , node ₁₀ , node ₁₁ , node ₁₃ }. In the entire geographical hierarchy tree, the path formed by the candidate links is represented by a dotted line. There are three candidate address links L = { _l1 , _l2 , _l3 }:

l1＝<root,node ₂ ,node ₅ >

l2＝<root,node ₁ ,node ₄ ,node ₇ ,node ₁₁ >

l3＝<root,node ₁ ,node ₄ ,node ₆ ,node ₁₀ ,node ₁₃ >

The text representations corresponding to the above three candidate address links are [province]-[city 2]-[point of interest 1], [province]-[city 1]-[district 2]-[street 2]-[point of interest 3] and [province]-[city 1]-[district 2]-[street 1]-[community 2]-[community 2]. L = {l ₁ ,l ₂ ,l ₃ } covers all matching hierarchical nodes M = {root,node ₄ ,node ₅ ,node ₁₀ ,node ₁₁ ,node ₁₃ }. The hierarchical node with the largest level value in each candidate link is called the terminal node of the link. The terminal nodes corresponding to the above three address links l ₁ ,l ₂ ,l ₃ are node ₅ ,node ₁₁ ,node ₁₃ respectively.

To obtain the terminal nodes of all candidate links, the entire geographical hierarchy tree is traversed in depth-first order, which can be achieved through a recursive process:

S0: Given a matching node set M, a geographical tree T<V,E,root>, assign the root node root to currNode

S1: Initialize the terminal node set under the subtree with currNode as the root to S = {}

S2: Get the child node set of currNode: children = {node _i | node _i .parent = currNode}

S3: If childrens is empty and currNode∈M, then S.add(currNode) and return S, exit the current call and go to S5

S4: traverse each node node _i in childrens, assign node _i to currNode, perform a recursive call and go to S1

S5: Add the returned terminal node set S′ to S

S6: If S is empty and currNode∈M, then S.add(currNode)

S7: If currNode = root, end the recursion and return to S; otherwise, return to S, exit the current call and go to S5

Through the above recursive process, we finally get the set S of all terminal nodes under the subtree of the root node root.

Step 205: Calculate the score of each candidate address link according to the score values of the hierarchical nodes included in the candidate address link, and select the candidate address link with the highest score as the placement result.

In this embodiment, by calculating the link scores of all candidate address links, the address link with the largest score is selected as the final query placement result. The address link score is calculated from the scores of the matching hierarchical nodes in the candidate links. The larger the address link score, the higher the degree of match with the query content.

The score values of the hierarchical nodes included in the candidate address link may be directly accumulated as the score of the candidate address link.

In some optional implementations of this embodiment, for each hierarchical node included in the candidate address link, the score value of the hierarchical node is weighted by the hierarchical weight; the weighted values of the score values of all hierarchical nodes included in the candidate address link are accumulated as the score of the candidate address link.

Define the calculation method of the address link matching score LinkScore. Given a query address text q and a candidate address link link _i = <node ₁ , ..., node _k , ..., node _s >, where node _k represents the kth level node in the candidate link link _i in ascending order of level, the address link matching score is:

Where log(node _k .level) represents the hierarchical weight. In the address link, the weight of the hierarchical node with a larger level value is higher. NodeScore(node _k ,q) represents the matching score between the query text q and the hierarchical node node _k . Its definition is shown in formula (2).

By traversing each candidate address link and calculating the link score according to the above definition, and recording the address link with the maximum score, the result with the maximum link score value is finally returned to the user as the placement result.

The method provided by the above embodiment of the present disclosure designs a matching method based on sliding window slicing for geographic hierarchical data, obtains query word matching hierarchical nodes by performing n-gram sliding window slicing on the query text, and realizes fuzzy matching of geographic hierarchical data. The present disclosure designs a score calculation method based on a hierarchical structure, realizes the ranking of the matching degree of all candidate address links, and returns the candidate address link with the highest score based on the ranking result.

Further referring to FIG3 , it shows a process 300 of another embodiment of the address location method. The process 300 of the address location method includes the following steps:

Step 301, perform sliding window slicing on the address text to obtain a word unit set.

Step 302: query the pre-built inverted index for each word in the word set to obtain all hierarchical nodes containing the word, and obtain matching hierarchical nodes.

Step 303: For each matched level node, a score value of the level node is calculated according to the weight of the matched word.

Step 304: Obtain all candidate address links containing matching hierarchical nodes through depth-first traversal.

Step 305: Calculate the score of each candidate address link according to the score values of the hierarchical nodes included in the candidate address link, and select the candidate address link with the highest score as the placement result.

Steps 301, 303-305 are substantially the same as steps 201, 203-205, and thus will not be described in detail.

The process of pre-building an inverted index has been introduced above. Step 302 is to quickly query the hierarchical nodes by querying the pre-built inverted index.

The query efficiency is optimized for the hierarchical node matching process. By matching the geographical hierarchical tree with the query word W = {w ₁ ,…,w _j ,…,w _k }, step 202 is implemented by traversing all hierarchical nodes V = {node ₁ ,…,node _i ,…,node _n } in turn and judging whether they meet the conditions. If it matches, the node is added to the matching node set M. The time complexity of the whole process is O(n*k). In step 302, the hierarchical node matching operation can be quickly completed through the pre-built word inverted index structure, that is, the inverted index Index(·) is queried for the word w _j to obtain the hierarchical node list Index(w _j ) matching the word, and the Index(w _j ) corresponding to the word is directly added to M, that is, M=M∪Index(w _j ). The time complexity of the inverted index query is O(1), and the time complexity of the whole process can be reduced to O(k).

By combining database technology and full-text retrieval technology, we design term inverted index and term weight index to accelerate the address location matching process and reduce query time.

Continuing to refer to FIG. 4a, FIG. 4a is a schematic diagram of an application scenario of the address location method according to the present embodiment. In the application scenario of FIG. 4a, the data initialization process is first performed. The device constructs an inverted index based on standard geographic hierarchical data. The index structure is a key-value type data structure. The key is a text fragment (called a word element) obtained by sliding window slicing the hierarchical node name, and the value is a list of all hierarchical nodes containing the word element. This inverted index structure can quickly locate all hierarchical nodes containing the word element by querying the word element. After the inverted index is constructed, the weight of the word element is calculated according to the frequency of each word element in the geographic hierarchical data. The weight reflects the importance of the word element (that is, the higher the frequency of occurrence, the lower the importance of the word element). The preparation of the device is completed after the inverted index is constructed and the word element weight is calculated. It is worth noting that the data initialization process only needs to be run once when the device is started, and the processed inverted index and term weight are stored in the cache. The address location process can be performed unlimited times later.

Then, the address placement process is executed. The address text queried by the user is input, and first, the query address text is sliced by sliding window to obtain word units. This operation is consistent with the operation of sliding window slicing of the hierarchical node name during the data initialization process. Then, the inverted index pre-built by the word unit query is used to obtain all hierarchical nodes containing the word unit, thereby realizing the hierarchical node matching operation. All matched hierarchical nodes and matching information are obtained, and the score value of each matched hierarchical node is calculated based on the word unit weight, word unit length, and matching ratio of the hierarchical node. Then, all candidate address links containing matching hierarchical nodes are obtained through depth-first traversal. The link is an ordered sequence of hierarchical nodes from the root node to the matching terminal node. Finally, the score of the entire address link is calculated based on the hierarchical node information contained in the candidate address link, and the address link with the highest score is selected as the placement result and returned to the user.

Further referring to FIG. 5 , as an implementation of the methods shown in the above figures, the present disclosure provides an embodiment of an address placement device, which corresponds to the method embodiment shown in FIG. 2 , and can be specifically applied to various electronic devices.

As shown in Fig. 5, the address placement device 500 of this embodiment includes: a word segmentation unit 501, a matching unit 502, a calculation unit 503, a link unit 504 and a selection unit 505. The word segmentation unit 501 is configured to perform sliding window slicing on the address text to obtain a word unit set; the matching unit 502 is configured to match the word unit set with the hierarchical node data in the geographical hierarchical tree to obtain a matched hierarchical node, wherein the hierarchical node data includes: a word unit set obtained by sliding window slicing the hierarchical node name; the calculation unit 503 is configured to calculate the score value of each matched hierarchical node according to the weight of the matched word unit; the link unit 504 is configured to obtain all candidate address links containing matched hierarchical nodes through depth-first traversal; the selection unit 505 is configured to calculate the score of each candidate address link according to the score value of the hierarchical node contained in the candidate address link, and select the candidate address link with the highest score as the placement result.

In this embodiment, the specific processing of the word segmentation unit 501, matching unit 502, calculation unit 503, link unit 504 and selection unit 505 of the address placement device 500 can refer to steps 201, 202, 203, 204 and 205 in the corresponding embodiment of Figure 2.

In some optional implementations of this embodiment, the matching unit 502 is further configured to: query the pre-constructed inverted index for each word in the word set to obtain all hierarchical nodes containing the word, and obtain matching hierarchical nodes.

In some embodiments, the device also includes an inverted index unit (not shown in the drawings), which is configured to: for each hierarchical node in the geographic hierarchical tree, perform sliding window slicing on the node name to obtain a corresponding fuzzy word set; for each fuzzy word in the fuzzy word set, register all hierarchical nodes containing the fuzzy word into the inverted index of the word.

In some embodiments, the device also includes a weight calculation unit (not shown in the drawings), which is configured to calculate the weight of the word based on the frequency of each word in the word set appearing in the hierarchical node data in the geographic hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight.

In some embodiments, the calculation unit 503 is further configured to: calculate the score value of the level node according to the word unit weight, word unit length, and the matching ratio of the level node.

In some embodiments, the link unit 504 is further configured to: for each hierarchical node included in the candidate address link, weight the score value of the hierarchical node by the hierarchical weight; and accumulate the weighted values of the score values of all hierarchical nodes included in the candidate address link as the score of the candidate address link.

In some embodiments, the device also includes a weight index unit (not shown in the drawings), which is configured to: before calculating the score value of the hierarchical node based on the weight of the matching word, query the weight of the matching word through a pre-generated word weight index; wherein the word weight index is generated through the following steps: for each hierarchical node in the geographic hierarchical tree, the node name is sliced by sliding window to obtain the corresponding fuzzy word set; the weight of the fuzzy word is calculated according to the frequency of occurrence of each fuzzy word in the fuzzy word set in the hierarchical node data in the geographic hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight; the weight of each fuzzy word is stored in a key-value type data structure to generate a word weight index.

It should be noted that the collection, collection, updating, analysis, processing, use, transmission, storage and other aspects of user personal information involved in the technical solution of this disclosure are in compliance with the provisions of relevant laws and regulations, are used for legitimate purposes, and do not violate public order and good morals. Necessary measures are taken for user personal information to prevent illegal access to user personal information data and maintain the security of user personal information, network security and national security.

According to an embodiment of the present disclosure, the present disclosure also provides an electronic device and a readable storage medium.

An electronic device comprises: one or more processors; a storage device on which one or more computer programs are stored, and when the one or more computer programs are executed by the one or more processors, the one or more processors implement the method described in process 200 or 300.

A computer-readable medium stores a computer program, wherein the computer program implements the method described in process 200 or 300 when executed by a processor.

FIG6 shows a schematic block diagram of an example electronic device 600 that can be used to implement an embodiment of the present disclosure. The electronic device is intended to represent various forms of digital computers, such as laptop computers, desktop computers, workbenches, personal digital assistants, servers, blade servers, mainframe computers, and other suitable computers. The electronic device can also represent various forms of mobile devices, such as personal digital processing, cellular phones, smart phones, wearable devices, and other similar computing devices. The components shown herein, their connections and relationships, and their functions are merely examples and are not intended to limit the implementation of the present disclosure described and/or required herein.

As shown in Figure 6, the device 600 includes a computing unit 601, which can perform various appropriate actions and processes according to a computer program stored in a read-only memory (ROM) 602 or a computer program loaded from a storage unit 608 into a random access memory (RAM) 603. In the RAM 603, various programs and data required for the operation of the device 600 can also be stored. The computing unit 601, the ROM 602, and the RAM 603 are connected to each other via a bus 604. An input/output (I/O) interface 605 is also connected to the bus 604.

A number of components in the device 600 are connected to the I/O interface 605, including: an input unit 606, such as a keyboard, a mouse, etc.; an output unit 607, such as various types of displays, speakers, etc.; a storage unit 608, such as a disk, an optical disk, etc.; and a communication unit 609, such as a network card, a modem, a wireless communication transceiver, etc. The communication unit 609 allows the device 600 to exchange information/data with other devices through a computer network such as the Internet and/or various telecommunication networks.

The computing unit 601 may be a variety of general and/or special processing components with processing and computing capabilities. Some examples of the computing unit 601 include, but are not limited to, a central processing unit (CPU), a graphics processing unit (GPU), various dedicated artificial intelligence (AI) computing chips, various computing units running machine learning model algorithms, digital signal processors (DSPs), and any appropriate processors, controllers, microcontrollers, etc. The computing unit 601 performs the various methods and processes described above, such as a road area planning method. For example, in some embodiments, the road area planning method may be implemented as a computer software program, which is tangibly contained in a machine-readable medium, such as a storage unit 608. In some embodiments, part or all of the computer program may be loaded and/or installed on the device 600 via the ROM 602 and/or the communication unit 609. When the computer program is loaded into the RAM 603 and executed by the computing unit 601, one or more steps of the road area planning method described above may be performed. Alternatively, in other embodiments, the computing unit 601 may be configured to perform the road area planning method in any other appropriate manner (e.g., by means of firmware).

Various implementations of the systems and techniques described above herein can be implemented in digital electronic circuit systems, integrated circuit systems, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), application specific standard products (ASSPs), systems on chips (SOCs), load programmable logic devices (CPLDs), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include: being implemented in one or more computer programs that can be executed and/or interpreted on a programmable system including at least one programmable processor, which can be a special purpose or general purpose programmable processor that can receive data and instructions from a storage system, at least one input device, and at least one output device, and transmit data and instructions to the storage system, the at least one input device, and the at least one output device.

The program code for implementing the method of the present disclosure may be written in any combination of one or more programming languages. These program codes may be provided to a processor or controller of a general-purpose computer, a special-purpose computer, or other programmable data processing device, so that the program code, when executed by the processor or controller, implements the functions/operations specified in the flow chart and/or block diagram. The program code may be executed entirely on the machine, partially on the machine, partially on the machine and partially on a remote machine as a stand-alone software package, or entirely on a remote machine or server.

In the context of the present disclosure, a machine-readable medium may be a tangible medium that may contain or store a program for use by or in conjunction with an instruction execution system, device, or equipment. A machine-readable medium may be a machine-readable signal medium or a machine-readable storage medium. A machine-readable medium may include, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, device, or equipment, or any suitable combination of the foregoing. A more specific example of a machine-readable storage medium may include an electrical connection based on one or more lines, a portable computer disk, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber, a portable compact disk read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.

To provide interaction with a user, the systems and techniques described herein can be implemented on a computer having: a display device (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user; and a keyboard and pointing device (e.g., a mouse or trackball) through which the user can provide input to the computer. Other types of devices can also be used to provide interaction with the user; for example, the feedback provided to the user can be any form of sensory feedback (e.g., visual feedback, auditory feedback, or tactile feedback); and input from the user can be received in any form (including acoustic input, voice input, or tactile input).

The systems and techniques described herein may be implemented in a computing system that includes back-end components (e.g., as a data server), or a computing system that includes middleware components (e.g., an application server), or a computing system that includes front-end components (e.g., a user computer with a graphical user interface or a web browser through which a user can interact with implementations of the systems and techniques described herein), or a computing system that includes any combination of such back-end components, middleware components, or front-end components. The components of the system may be interconnected by any form or medium of digital data communication (e.g., a communications network). Examples of communications networks include: a local area network (LAN), a wide area network (WAN), and the Internet.

A computer system may include a client and a server. The client and the server are generally remote from each other and usually interact through a communication network. The relationship between the client and the server is generated by computer programs running on the respective computers and having a client-server relationship with each other. The server may be a server of a distributed system, or a server combined with a blockchain. The server may also be a cloud server, or an intelligent cloud computing server or intelligent cloud host with artificial intelligence technology. The server may be a server of a distributed system, or a server combined with a blockchain. The server may also be a cloud server, or an intelligent cloud computing server or intelligent cloud host with artificial intelligence technology.

It should be understood that the various forms of processes shown above can be used to reorder, add or delete steps. For example, the steps recorded in this disclosure can be executed in parallel, sequentially or in different orders, as long as the desired results of the technical solutions disclosed in this disclosure can be achieved, and this document does not limit this.

The above specific implementations do not constitute a limitation on the protection scope of the present disclosure. It should be understood by those skilled in the art that various modifications, combinations, sub-combinations and substitutions can be made according to design requirements and other factors. Any modification, equivalent substitution and improvement made within the spirit and principle of the present disclosure shall be included in the protection scope of the present disclosure.

Claims (10)

1. A method for address placement, comprising: Slice the address text through sliding windows to obtain a word-unit set; Matching the word-gram set with the hierarchical node data in the geographical hierarchical tree to obtain matching hierarchical nodes, wherein the hierarchical node data includes: a word-gram set obtained by sliding window slicing of the hierarchical node name; For each matched level node, the score value of the level node is calculated according to the weight of the matched word; Obtain all candidate address links containing matching hierarchical nodes through depth-first traversal; The score of each candidate address link is calculated according to the score values of the hierarchical nodes contained in the candidate address link, and the candidate address link with the highest score is selected as the placement result. 2. The method according to claim 1, wherein the step of matching the word set with the hierarchical node data in the geographical hierarchical tree to obtain the matching hierarchical nodes comprises: For each word in the word set, a pre-built inverted index is queried to obtain all hierarchical nodes containing the word, and a matching hierarchical node is obtained. 3. The method according to claim 2, wherein the method further comprises: For each level node in the geographical level tree, the node name is sliced by sliding window to obtain the corresponding fuzzy word set; For each fuzzy word-gram in the fuzzy word-gram set, all hierarchical nodes containing the fuzzy word-gram are registered in the inverted index of the word-gram. 4. The method according to claim 1, wherein the method further comprises: The weight of each word in the word set is calculated according to the frequency of occurrence of each word in the hierarchical node data in the geographical hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight. 5. The method according to claim 1, wherein the step of calculating the score value of the level node according to the weight of the matched word-element comprises: The score value of the level node is calculated based on the word unit weight, word unit length, and the matching ratio of the level nodes. 6. The method according to claim 1, wherein the step of calculating the score of each candidate address link according to the score values of the hierarchical nodes included in the candidate address link comprises: For each level node included in the candidate address link, the score value of the level node is weighted by the level weight; The weighted values of the score values of all level nodes included in the candidate address link are accumulated as the score of the candidate address link. 7. The method according to claim 1, wherein before calculating the score value of the level node according to the weight of the matched word-gram, the method further comprises: Query the weight of the matching word through the pre-generated word weight index; The word unit weight index is generated by the following steps: For each level node in the geographical level tree, the node name is sliced by sliding window to obtain the corresponding fuzzy word set; Calculate the weight of the fuzzy word according to the frequency of occurrence of each fuzzy word in the fuzzy word set in the hierarchical node data in the geographical hierarchical tree, wherein the higher the frequency of occurrence, the lower the weight; The weight of each fuzzy word is stored in a key-value data structure to generate a word weight index. 8. An address placement device, comprising: A word segmentation unit is configured to perform sliding window slicing on the address text to obtain a word unit set; A matching unit is configured to match the word-gram set with the hierarchical node data in the geographical hierarchical tree to obtain a matched hierarchical node, wherein the hierarchical node data includes: a word-gram set obtained by sliding window slicing the hierarchical node name; A calculation unit is configured to calculate, for each matched level node, a score value of the level node according to the weight of the matched word element; The link unit is configured to obtain all candidate address links containing matching hierarchical nodes through depth-first traversal; The selection unit is configured to calculate the score of each candidate address link according to the score values of the hierarchical nodes included in the candidate address link, and select the candidate address link with the highest score as the placement result. 9. An electronic device comprising: one or more processors; a storage device having one or more computer programs stored thereon, When the one or more computer programs are executed by the one or more processors, the one or more processors implement the method according to any one of claims 1 to 7. 10. A computer-readable medium having a computer program stored thereon, wherein the computer program implements the method according to any one of claims 1 to 7 when executed by a processor.