BRPI0709707A2 - Índices de localidade e mÉtodo para indexar localidades - Google Patents

Abstract

ÍNDICES DE LOCALIDADE E MÉTODO PARA INDEXAR LOCALIDADES Índices de localidade são apresentados para uso com bancos de dados e mapas eletrônicos. Cada aspecto geográfico em um banco de dados geográfico é associado a nomes de localidade a partir de várias fontes de nome de localidade. Tokenização, normalização, otimização e casamento sensíveis ao contexto, de nomes de localidade, eliminam nomes de localidade duplicatas e variantes, enquanto preservam nomes significativamente diferentes. Uma tabela de nomes de localidade inclui a representação analisada de cada nome de localidade e outras informações associadas, e um token primário para indexação é identificado. Uma máscara de fonte principal é criada por alocar um bit para cada fonte de nome de localidade utilizada no método. Uma máscara de fonte separada é armazenada para cada aspecto geográfico associado a uma localidade, um conjunto de bits para cada fonte na qual a localidade pode ser encontrada. Nomes de localidade associados a cada aspecto geográfico são indexados em uma tabela de aspectos geográficos em ordem de prevalência para uso em uma dada aplicação.

Description

"ÍNDICES DE LOCALIDADE E MÉTODO PARA INDEXAR LOCALIDADES"

Reivindicação de prioridadeO pedido de patente US número 11/433.104, intitulado LOCALITY INDEXES ANDMETHOD FOR INDEXING LOCALITIES, de Michael Gelich, depositado em 12 de maio de2006 (número do dossiê do procurador TELA-07767USO).

CAMPO DA INVENÇÃO

A presente invenção refere-se a índices de localidades para bancos de dadosgeográficos, e mais particularmente a estruturas de dados em bancos de dados geográficosutilizados para indexar nomes de localidade e características geográficas associadascontidas nas localidades.

ANTECEDENTES DA INVENÇÃO

Nos últimos anos, os consumidores foram dotados de uma variedade dedispositivos e sistemas para permitir aos mesmos localizar endereços de rua específicos emum mapa digital. Esses dispositivos e sistemas têm a forma de sistemas de navegação noveículo que permitem aos motoristas navegar por ruas e estradas, dispositivos portáteiscomo assistentes pessoais digitais ("PDAs"), dispositivos de navegação pessoais e telefonescelulares que podem fazer o mesmo, e aplicações de Internet nas quais usuários podemgerar mapas mostrando localizações desejadas. O aspecto comum em todos esses e outrostipos de dispositivos e sistemas é um banco de dados geográficos de característicasgeográficas e software para acessar e manipular o banco de dados geográficos em respostaa entradas de usuário. Essencialmente, em todos esses dispositivos e sistemas um usuáriopode entrar uma localização alvo e o resultado retornado será a posição da localização alvo.

Tipicamente, os usuários entrarão um endereço, o nome de uma firma, como umrestaurante, um centro de cidade, ou um marco de destino, como a Ponte Golden Gate, eentão receberão a localização do lugar solicitado, ou característica. A localização pode sermostrada em uma exibição de mapa, ou pode ser utilizada para calcular e exibir orientaçõesde direção até o local ou utilizada de outras maneiras.

Tipicamente, aplicações utilizam métodos de busca top-down que buscam alocalidade na qual uma característica geográfica desejada está localizada, a seguir buscama característica geográfica naquela localidade. Os exemplos de características geográficasque podem ser encontradas em uma localidade são endereços, marcos e locais comerciais.As aplicações utilizam também métodos de busca bottom-up que buscam todas ascaracterísticas geográficas que casam com certos critérios, a seguir escolhem acaracterística geográfica desejada a partir da lista de localidades na qual as característicasgeográficas casadas estão localizadas.

Atualmente, bancos de dados geográficos não são abastecidos com índices delocalidade ou têm índices de localidade que são de funcionalidade limitada ao buscarcaracterísticas geográficas em localidades. Um índice de localidade pode ser utilizado paraselecionar um nome de localidade e informações associadas para exibição para um usuário.

Uma localidade é, por exemplo, uma cidade ou cidade pequena em um estado (EUA),província (Canadá), condado ou outra característica geográfica principal. Para bancos dedados geográficos atualmente tendo índices de localidade, os índices são basicamentelistas de nomes de localidade, ordenados por fonte de nomes, com duplicação de nomesentre fontes. Nomes de localidades podem ser encontrados em muitas fontes de nomes delocalidade, como fontes administrativa, postal e coloquial. O termo "nome de localidade"nesse pedido é utilizado para se referir a qualquer dado que pode ser utilizado como umadescrição de localidade. Além das fontes listadas acima, os próprios códigos postais podemser utilizados como nomes de localidade. Também números de centrais de telefone indicamlocalidade em alguns países e podem ser utilizados como nomes de localidade. NaAlemanha, prefixos de placa de licença de carro indicam localidade e podem ser utilizadoscomo nomes de localidade. O que se segue é uma discussão de estado da técnica de bancode dados geográficos independente de se um banco de dados geográfico é fornecido ou nãocom um índice de localidade.

Atualmente, um banco de dados geográfico povoado com informações delocalidade a partir de várias fontes de nome de localidade conterá entradas duplicatas parauma localidade se o nome de localidade aparecer em múltiplas fontes de nome delocalidade. Os fabricantes de sistema ou dispositivo ou desenvolvedores de aplicações nãofundem as localidades duplicatas em um único conjunto de nomes ou fazem uma fusãoincompleta devido a diferenças na representação das duplicatas através de fontes delocalidade, como soletração, pontuação, abreviatura ou outras diferenças entre asduplicatas. Desse modo, quando um usuário consulta então uma aplicação de banco dedados geográficos para uma localidade, o sistema ou dispositivo do usuário pode listar omesmo nome de localidade múltiplas vezes se o nome de localidade aparecer em múltiplasfontes de nome de localidade. Isso é confuso para o usuário que deve escolher entre nomesidênticos ou quase idênticos exibidos para a tela do dispositivo ou sistema do usuário. Existeum problema adicional na lista de nomes de localidade se o usuário for incapaz dediferenciar entre localidades duplicatas efetivas e localidades separadas tendo nomes iguaisou levemente variantes. O problema de nomes de localidade duplicatas a partir de múltiplasfontes de nomes de localidade é exacerbado em alguns dispositivos de navegação que têmmemória limitada. Por exemplo, alguns dispositivos podem conter somente dois nomes delocalidade por característica geográfica. Para uma característica geográfica associada amais de dois nomes de localidade, qualquer seleção de dois dos nomes de localidade parausar no dispositivo pode ser inferiores à ótima porque localidades que são duplicatas porémseparadas e localidades tendo nomes de localidade mais prevalentes podem estar ausentesna seleção. Uma localidade separada duplicata ausente pode levar um usuário a pegar umalocalidade incorreta devido a sua exclusividade aparente em uma lista. Para bancos dedados geográficos tendo índices de localidade, a falha em fundir localidades duplicatastambém cria índices de localidade que são de difícil controle em tamanho, especialmentepara dispositivos de navegação de memória limitada.

Atualmente, para localidades tendo nomes iguais ou levemente variantes quecompartilham as mesmas características geográficas exatas, entradas de nome duplicatasnão são eliminadas a partir de índices de localidade da técnica anterior. Para localidadestendo nomes iguais ou levemente variantes que compartilham pelo menos umacaracterística geográfica, as entradas de nome não são fundidas em uma única entrada emíndices de localidade da técnica anterior. Um banco de dados geográfico povoado cominformações de localidade a partir de várias fontes de nome de localidade pode conternomes levemente variantes para uma localidade se pelo menos duas das fontes diferentestiverem nomes levemente variantes para a localidade. Por exemplo, Ho-Ho-Kus, NovaJérsei, é conhecida por nomes levemente diferentes em diferentes fontes, como Ho-Ho-Kus,Ho Ho Kus ou Ho-Ho-Kus (Hohokus). Para índices de localidade da técnica anterior, a falhaem eliminar entradas de banco de dados geográficos tendo nomes de localidade levementevariantes cria índices de localidade que são de difícil controle em tamanho, especialmentepara dispositivos de navegação de memória limitada, e confusão para usuários que tentamdistinguir entre esses nomes de localidade levemente diferentes. Para localidades de nomeduplicata ainda assim separadas, a técnica anterior distingue atualmente entre aslocalidades por exibir informações adicionais, como o condado no qual a localidade estálocalizada. Para essas localidades, cidades próximas, bem conhecidas ou prevalentesexibidas como informações adicionais com as localidades seriam mais úteis para um usuárioporque nomes de cidade e localizações são mais prováveis de serem reconhecíveis para ousuário do que nomes de condado nos EUA.

A Figura 1 ilustra um diagrama mostrando um exemplo de definições de localidadeque não são tratadas de forma consistente em uso comum. Os exemplos de definições delocalidade são "local postal" e "subdivisão de condado". Na Figura 1, em uso comum, Allstoné considerado como sendo parte de Boston. Allston é mostrado contido na Subdivisão decondado: Boston. Ao contrário, Manhattan é considerado como sendo parte da Cidade deNova York, porém Manhattan é uma Subdivisão de Condado e Cidade de Nova York é umLocal postal bem como um Local Incorporado. Na Figura 1, Subdivisão de condado:Manhattan é mostrado contido no Local postal: Cidade de Nova York. Tais contradiçõesilustram a diferença entre definições de uso comum e localidade formal.

Além disso, em outro exemplo de definições de localidade que não são tratadasconsistentemente em uso comum, certas características geográficas no estado de NovaYork estão contidas nas localidades parcialmente em sobreposição conhecidas em usocomum como SoHo1 Manhattan e Cidade de Nova York. Como mencionado acima, a cidadede Nova York pode ser encontrada em uma fonte de nome de localidade de Local Postal, eManhattan pode ser encontrado em uma fonte de nome de localidade de Local incorporado.SoHo, por outro lado, não pode ser encontrado em uma fonte de nome de localidade e éconhecido coloquialmente. SoHo estará ausente em um índice de localidade com basesomente em definições de localidade formal.

Além disso, índices de localidade de banco de dados geográficos atuais não sãoordenados por prioridade, ou sua importância para uso comum. Além disso, para cadacaracterística geográfica em um banco de dados geográfico, localidades associadas a umacaracterística geográfica não são priorizadas para a característica geográfica. Para umdispositivo de memória limitada que pode armazenar somente alguns nomes de localidadepara cada característica geográfica, sem priorização de localidades, um desenvolvedor deaplicações deve escolher alguns nomes de localidade para uma característica geográficaassociada a mais de algumas localidades. Preferivelmente, as localidades de prioridademais elevada associadas a uma característica geográfica, ou aquelas localidades que sãoas mais conhecidas ou mais prevalentes em uso comum, seriam exibidas para o dispositivode um usuário. Ao apresentar uma lista de localidades para um usuário, os nomes deprioridade mais elevada associados a características geográficas devem ser utilizados umavez que serão os mais reconhecíveis.

Além disso, o componente de nome mais importante, ou token primário, de umnome de localidade, como "Hadley" no nome "South Hadley", não é identificado em algunsíndices de localidade de banco de dados geográfico atuais. Quando algumas aplicações denavegação atualmente comercialmente disponíveis buscam a cidade Hadley emMassachusetts, Hadley é recuperado, porém South Hadley não é recuperado. Paraencontrar South Hadley, o usuário tem de iniciar com "S" e separar através de muitasopções que começam com "South".

Um índice de localidade de banco de dados geográfico é necessário de tal modoque nomes de localidade duplicatas e localidades conhecidas por nomes levementevariantes são fundidos, se e somente se representarem a mesma localidade, para eliminarconfusão para um usuário que deve de outro modo escolher entre uma lista de nomesidênticos ou levemente variantes, especialmente para dispositivo de memória limitada. Umtal índice de localidade também é necessário para reduzir o tamanho do índice de outromodo de difícil controle. Embora faça a fusão de localidades com nomes variantes eduplicatas, há também necessidade de preservar nomes de localidade significativamentediferentes. Um índice de localidade é necessário de tal modo que nomes de localidadeduplicatas que representam localidades separadas são distinguidos. De outro modo, ousuário não tem meio para diferenciar dois lugares diferentes com o mesmo nome. Alémdisso, um índice de localidade flexível é necessário de tal modo que definições de localidadeformais não tratadas consistentemente em uso comum são consideradas, e de tal modo queo índice não se baseia nessas definições de localidade formais. Um índice de localidade énecessário que é ordenado por prioridade de localidade para cada característica geográficaassociada a múltiplas localidades. A ordenação por prioridade permite que nomes maisimportantes sejam escolhidos para serem incluídos em aplicações de memória limitada eidentifica o melhor nome para apresentar ao usuário. Finalmente, um índice de localidade énecessário de tal modo que o componente de nome mais importante para uma localidadefaz parte do índice para assegurar que uma busca para o componente de nome retornaráuma lista expandida de todas as localidades relevantes.

SUMÁRIO DA INVENÇÃO

Descrito em termos gerais, um índice de localidade é provido para uso com mapaseletrônicos e bancos de dados eletrônicos, bem como um método e sistema para criar oíndice.

Nomes de localidade a partir de várias fontes de nomes de localidade sãoassociados a características geográficas para cada característica geográfica em um bancode dados geográfico. Tokenização sensível a contexto, normalização, otimização ecasamento de nomes de localidade permitem eliminação e fusão de nomes de localidadeduplicatas e variantes, enquanto preserva nomes significativamente diferentes. Nomes delocalidade duplicatas são eliminados, se e somente se representarem a mesma localidade,para reduzir confusão para um usuário que deve de outro modo escolher entre uma lista denomes idênticos ou similares. Entradas de banco de dados geográfico para localidadesconhecidas por nomes levemente variantes são fundidas em uma única entrada se aslocalidades compartilharem pelo menos uma característica geográfica em comum.Localidades separadas tendo nomes de localidade duplicatas ou levemente variantes sãodistinguidas por adornar as mesmas com o nome de uma localidade próxima se e somentese representarem localidades diferentes, novamente para reduzir confusão para um usuárioque deve de outro modo escolher entre uma lista de nomes idênticos, ou nomes que sãodistinguidos em modos que são menos significativos para o usuário, por exemplo, poradornar com nomes de condado cujas localizações não são genericamente conhecidas paraos usuários.

Uma tabela de nome de localidade é criada e inclui o nome completo da localidade,o token primário da localidade para indexar e outras informações associadas, como umadorno, informações de centro de cidade e tamanho da localidade. Uma máscara de fonteprincipal é criada por alocar um bit para cada fonte de nome de localidade utilizada nométodo. Para cada característica geográfica em uma tabela de prioridade de localidade decaracterística, uma máscara de fonte separada é armazenada para cada localidadeassociada à característica geográfica, um conjunto de bits para cada fonte na qual alocalidade pode ser encontrada. Nessa tabela estão links com a tabela de nome delocalidade e uma prioridade para cada localidade associada a uma característica geográfica.

A tabela de localidade de característica também inclui links com a tabela de encontrarcaracterística, que inclui informações de características geográficas associadas para cadacaracterística geográfica.

Os nomes de localidade para cada característica geográfica são indexados emordem de prioridade. Na modalidade preferida, a localidade de prioridade mais elevadaassociada a uma característica geográfica é aquela encontrada em uma fonte de nomepostal preferido, a seguir a prioridade das localidades restantes é determinada pelo númerode conjunto de bits em cada máscara de fonte de localidade. Em um tal índice, uma primeiralocalidade tem uma prioridade mais elevada do que a segunda localidade se a primeiralocalidade for mais conhecida ou prevalente em uso comum.

A ordenação por prioridade permite que nomes mais importantes sejam escolhidospara serem incluídos em aplicações de memória limitada e identifica o melhor nome paraapresentar para o usuário em uma busca bottom-up. O tamanho de difícil controle do índicede localidade que teria contido nomes de localidade duplicatas e levemente variantes édesse modo reduzido. Além disso, o índice de localidade leva em consideração definiçõesde localidade que não são tratadas consistentemente em uso comum porque o índice nãose baseia nessas definições de localidade formais. Finalmente, o componente de nome maisimportante para uma localidade a partir da etapa de tokenização é parte do índice paraassegurar que uma busca para o componente de nome retornará uma lista expandida detodas as localidades relevantes.

BREVE DESCRIÇÃO DOS DESENHOS

A Figura 1 ilustra um diagrama mostrando um exemplo de definições de localidadeque não são tratadas consistentemente em uso comum.

A Figura 2 ilustra um diagrama mostrando uma hierarquia de áreas administrativasdos Estados Unidos.

A Figura 3 ilustra um exemplo da necessidade de diferenciar entre endereços como mesmo nome, como "Adams Street" que são localizados em quatro localidades diferentesem uma localidade, como "Boston, Massachusetts."

A Figura 4 ilustra um exemplo de localidades oficiais e vizinhanças com o mesmonome como "Brentwood, Califórnia" que podem ser distinguidas através do uso de múltiplostipos de fontes de nome de localidade.

A Figura 5 ilustra um exemplo de pequenas aldeias que podem ser listadas emfontes oficiais porém que não têm limites claramente delineados, como "Quechee, Vermont"que são necessários para inclusão em um índice de localidade abrangente.

A Figura 6 ilustra um exemplo de vizinhanças, que são nomes de localidade nãooficiais, como "Greenwich Village" na Cidade de Nova York, que são necessários parainclusão em um índice de localidade abrangente.

A Figura 7 ilustra um exemplo de aldeias localizadas em uma circunscrição, como

"Forest Hills" na circunscrição de Queens na Cidade de Nova York, que são necessáriaspara inclusão em um índice de localidade abrangente.

As Figuras 8A e 8B mostram uma modalidade de um fluxograma de processo paraligar localidades a características geográficas em um banco de dados geográfico,tokenização, normalização, otimização e casamento de nomes de localidade e criação deum índice de localidades ordenadas por prioridade.

A Figura 9 ilustra um exemplo de votação de face utilizado para determinar umnome de localidade para uma rua associada a um nome de localidade desconhecido.

A Figura 10 mostra dois exemplos de máscaras de fonte de nome de localidadepara os Estados Unidos e para o Canadá.

A Figura 11 mostra uma modalidade de um algoritmo para reduzir o conjunto denomes de localidade através de casamento de nomes de localidade.

A Figura 12 mostra uma modalidade de um algoritmo para determinar a prioridadede nomes de localidade para uma dada característica geográfica.

A Figura 13 mostra uma modalidade de arquivos de índice de localidade incluindouma tabela de Prioridade de Localidade de característica, uma tabela de Nome delocalidade e uma tabela de Encontrar característica.

A Figura 14 ilustra um exemplo para o qual uma aplicação de navegação podeacomodar inconsistência quando uma cidade próxima é especificada de forma errônea.

A Figura 15 mostra um diagrama de blocos de um sistema exemplar que pode serutilizado com modalidades.

DESCRIÇÃO DETALHADA

Para criar um melhor índice de localidade, uma lista completa de nomes delocalidade deve primeiramente ser criada por coletar nomes a partir de uma variedade defontes de nomes de localidade, fontes de nomes de localidade administrativa, postal ecoloquial, entre outras. A utilização de nomes de localidade a partir de qualquer número etipo de fontes permite um esquema universal para dados internacionais. Sem essacaracterística somente um número fixo de fontes pode ser utilizado, como fontes de nomepostal ou administrativo, nomes importantes potencialmente ausentes e limitando os tipos defontes que podem ser utilizados em países diferentes.

Embora a linguagem utilizada nessa descrição seja específica para os EstadosUnidos, em modalidades, os mesmos princípios podem ser aplicados internacionalmentesomente com ajustes nominais. Os exemplos de equivalentes de fonte de nome delocalidade estrangeira incluem a Ordnance Survey and Royal Mail no Reino Unido, e StatsCan and Canada Post no Canadá.

Em modalidade, para um dado conjunto de fontes de nomes de localidade, umalista de nomes de localidades é tirada de cada fonte de nomes de localidade. Emmodalidades, as fontes são aquelas contendo localidades em um ou mais estadosselecionados, territórios, províncias, ou distritos, por exemplo. Na modalidade preferida, asfontes são aquelas contendo localidades nos Estados Unidos. Nos Estados Unidos, porexemplo, fontes de nomes de localidade incluem, porém não são limitadas a:

1. Federal Information Processing Standards 55 (FIPS55). Esse componente dobanco de dados United States Geological Survey (USGS) TIGER está no domínio público(http://geonames.usgs.gov/fips55.html). FIPS55 é uma fonte padrão que descreve estruturade localidade para localidades administrativas como definido pelo governo, por exemplo,códigos para lugares povoados nomeados, divisões de condado primário, e outraslocalizações dos Estados Unidos, Porto Rico e as áreas afastadas.

2. Arquivo de Estado/cidade do United States Postal Service (USPS). Esse arquivoé um componente do produto USPS ZIP+4. Esses nomes de cidade e estado sãoencontrados na gama de endereços ou nível de código ZIP. Códigos ZIP de cinco dígitos eextensões de quatro dígitos (ZIP+4) são tratados como nomes de localidade em um índice eapontam para o conjunto apropriado de nomes no Arquivo de estado/cidade USPS. Emboraseja genericamente somente um nome de localidade postal preferido para cada local, oserviço postal também inclui qualquer número de nomes de localidade postal permissível enão permissível para o mesmo local. Um nome de localidade postal "preferido" é o nomeque USPS recomenda para uso ao endereçar correspondência. Um nome de localidadepostal "permissível" é um nome suposto que o USPS aprovou e permite para entrega decorrespondência. Um nome de localidade postal "não permissível" é um que USPS nãopermite para entrega de correspondência. Em modalidades, o índice de localidade incluirátodos os nomes de localidade postal preferidos e permissíveis para cada característicageográfica.

3. Geographic Names Information System (GNIS) fornecido pelo United StatesGeological Survey (USGS). Esse é um banco de dados de domínio público de nomes delocalidade nos Estados Unidos, incluindo os cinqüenta estados e os territórios. GNIS listanomes de cidades, seus pontos centrais, suas populações e informações similares.

4. Pontos de interesses (POIs) para centros de cidades.

5. POIs para Agências de Correios USPS.

6. Sistema de Codificação e referência geográfico topologicamente integrado(TIGER) do United States Census Bureau Registro tipo C para entidade "P" (lugaresincorporado em TIGER).

7. TIGER Registro tipo C para entidade "M" (Subdivisões de condado em TIGER).

Nomes de localidade que são inteiramente contidos em um estado podem serassociados ao estado para fins de indexação. Localidades que não são inteiramentecontidas em um estado, como certos códigos postais nos Estados Unidos, podem serindexados múltiplos de acordo com seus estados de contenção. A Figura 2 ilustra umdiagrama que mostra uma hierarquia de áreas administrativas dos Estados Unidos. Essasáreas administrativas são inteiramente contidas nos grupos mostrados centralmente nodiagrama como Nação, Regiões, Divisões, Estados e Contados. Esse diagrama mostra quesubdivisões de condado estão contidas em contados. Lugares administrativos, mostradoscomo "Lugares" na Figura 2, são inteiramente contidos em um estado. Lugaresadministrativos podem atravessar fronteiras de condado e subdivisão de condado. Áreasmetropolitanas, áreas urbanas e mesmo códigos ZIP podem atravessar fronteiras de estado,e desse modo são somente inteiramente contidas na Nação, como mostrado na Figura 2.

A Figura 1 ilustra um diagrama de exemplo mostrando que localidades nos EstadosUnidos não podem ser automaticamente modeladas de forma útil para aplicações denavegação utilizando somente um conjunto fixo de regras para manipular nomes a partir demúltiplas fontes de localidade. Locais postais e subdivisões de condado são encontrados emfontes oficiais. Na Figura 1, em Massachusetts, o Local Postal de Allston é inteiramentecontido na Subdivisão de condado de Boston. Em Nova York, entretanto, a Subdivisão decondado de Manhattan é inteiramente contida no Lugar Postal da Cidade de Nova York.Desse modo, uma fonte de nome de localidade de Subdivisão de Condado não pode sernecessariamente utilizada para determinar Locais Postais em uma subdivisão de condadoespecífica. Similarmente, uma fonte de nome de localidade de Local Postal não pode sernecessariamente utilizada para determinar uma Subdivisão de condado em um local postalespecífico. O uso comum de nomes de localidade a partir de fontes diferentes varia com ageografia. Essa variação deve ser considerada ao indexar nomes de localidade a partir demúltiplas fontes.

Em modalidades, o seguinte exemplo de caso de uso, como utilizado por umusuário de uma aplicação de software ou dispositivo que acessa o banco de dadosgeográfico, ilustra os benefícios de utilizar nomes de localidade a partir de múltiplas fontespara construir um índice. Se somente uma fonte de nomes for utilizada, nomes importantessão omitidos. Nomes postais, nomes administrativos, e mesmo nomes coloquiais são todosimportantes.

Sem fontes de nome postal em índice:

Entrar estado -> Vermont

Entrar cidade -> QuecheeCidade não encontrada: Quechee

Com fontes de nome postal em índice:

Entrar estado -> Vermont

Entrar cidade -> Quechee

Encontrado ->

Quechee

Sem fontes de nome administrativo no índice:

Entrar estado -> Nova York

Entrar cidade -> Manhattan

Cidade não encontrada: "Manhattan"

Com fontes de nome administrativo no índice:

Entrar estado -> Nova York

Entrar cidade -> Manhattan

Encontrado: "Manhattan"

Em modalidades, os seguintes quatro exemplos de caso de uso mostram que outrobenefício de compilar nomes de localidade a partir de múltiplas fontes de nome delocalidade é diferenciar entre endereços de rua ambíguos em uma localidade. Uma cidadenos Estados Unidos pode ter endereços de rua duplicatas localizados em diferentes partesda cidade. Isso é especialmente verdadeiro em cidades grandes, como Boston,Massachusetts. Como mencionado acima, Boston pode ser encontrado como umaSubdivisão de condado na fonte de nome de localidade Administrativa FIPS55. Emmodalidades, o primeiro desses quatro exemplos de caso de uso mostra um caso nãoproblemático típico quando um endereço de rua específico é exclusivo em uma cidade, nãohá problema para fins de navegação, mesmo se a cidade for grande. Um exemplo disso éNewbury Street em Boston. Esse nome de rua tem dez quarteirões de comprimento e não éduplicado em nenhuma outra parte em Boston:

Com fontes de nome administrativo no índice:

Entrar estado -> Massachusetts

Entrar cidade -> Boston

Entrar rua -> Newbury Street // exclusivo independente de número de casa

Nesse ponto, o destino precisa espera mais entrada a partir do usuário, como umnúmero específico da rua, a interseção mais próxima ou o quarteirão mais próximo. Quandoa entrada é fornecida, um destino é localizado em um mapa para o usuário:

Entrar número de rua -> 173

Encontrado: "173 Newbury Street, Boston, Massachusetts"

Em modalidades, o segundo desses quatro exemplos de caso de uso ocorrequando o nome de rua é duplicado em uma cidade,porém o número da casa serve paratornar o destino exclusivo. Uma rua longa que se estende através de várias cidadesmenores em uma cidade grande é um tal exemplo. Por exemplo, Commonwealth Avenue seestende através de Boston, bem como de cidades menores de Allston e Chestnut Hill emBoston. Como mencionado acima, Boston é uma Subdivisão de condado em fonte de nome de localidade administrativa. Allston e Chestnut Hill são cidades pequenas que podem serencontradas em fontes de nome de localidade Postal sob códigos postais 02134 e 02467,respectivamente.

Sem fontes de nome administrativo no índice:

Entrar estado -> Massachusetts Entrar cidade -> Boston

Entrar rua -> Commonwealth Avenue

Entrar número de rua -> 2000

Número de rua não encontrado: "2000"Como Boston não é um nome postal legítimo para o código postal 02467, de acordo com o U.S. Postal Service, "2000 Commonwealth Ave., Chestnut Hill1 Massachusetts 02467"não é encontrado no exemplo acima para Boston embora Chestnut Hill seja uma cidadepequena dentro de Boston.

Com fontes de nome administrativo e postal no índice:

Entrar estado -> Massachusetts

Entrar cidade -> Boston

Entrar rua -> Commonwealth AvenueNesse ponto, verifica-se que Commonwealth Avenue se estende através de Boston,Allston e Chestnut Hill. O destino precisa espera mais entrada a partir do usuário, como umnúmero específico de rua, a interseção mais próxima ou o quarteirão mais próximo. Quando a entrada é fornecida, um destino é localizado em um mapa para o usuário:

Entrar número de rua -> 2000

Encontrado: "2000 Commonwealth Avenue, Chestnut Hill, Massachusetts"Em modalidades, o terceiro desses quatro exemplos de caso de uso, comoilustrado na Figura 3 é similar ao segundo exemplo de caso de uso, exceto que quatro Adams Streets diferentes podem ser encontradas em quatro localidades diferentes emBoston. A Figura 3 ilustra a necessidade de diferenciar entre endereços com o mesmonome, como "Adams Street", que são localizados em quatro localidades diferentes em umalocalidade, como Boston, Massachusetts:

Sem fontes de nome postal no índice: Entrar estado -> Massachusetts

Entrar cidade -> Boston

Entrar rua -> Adams StreetPor favor escolher entre ->

Adams St. Boston // a aplicação encontra quatroAdams St. Boston // Adams streets separadas na cidadeAdams St. Boston // de Boston e o usuário é incapazAdams St. Boston // de diferenciar entre essas quatro opções

Com fontes de nome postal no índice:

Entrar estado -> MassachusettsEntrar cidade -> BostonEntrar rua -> Adams Street

Por favor escolher entre ->

Adams St., CharlestownAdams St., Hyde ParkAdams St., RoxburyAdams St., Dorchester

Entrar número da rua -> // o usuário continua entrando o número da rua

Nesse exemplo de caso de uso, a aplicação processa cada entrada de usuárioantes de solicitar mais informações a partir do usuário. Em outras modalidades, para "Comfontes de nome postal no índice", o usuário entra a cidade de Boston, a rua de AdamsStreet, e um número de rua antes que a aplicação processe essas três entradas.Considerando que o número de rua não é duplicado nas cidades pequenas de Charlestown1Hyde Park1 Roxbury e Dorchester, o nome de rua e número serão encontrados para umadessas quatro cidades e indicados em um mapa para exibição para o usuário.

Em modalidades, o quarto desses quatro exemplos de caso de uso mostra quemesmo números de rua, por exemplo "2 Adams St.", são duplicados em ruas separadascom o mesmo nome em uma cidade. Nesse caso, a única resposta adequada é apresentarao usuário uma lista de cidades menores nas quais as duplicatas são localizadas, paraderivar um destino único. Desse modo, utilizando o exemplo a partir do terceiro exemplo decaso de uso acima:

Com fontes de nomes administrativo e postal no índice:

Entrar estado -> MassachusettsEntrar cidade -> BostonEntrar rua -> Adams StreetEntrar número de rua -> 2

Por favor escolher entre ->

2 Adams St., Charlestown2 Adams St., Hyde Park2 Adams St., Roxbury2 Adams St., DorchesterEm modalidades, e outro exemplo de caso de uso como ilustrado na Figura 4,localidades oficiais e vizinhanças com o mesmo nome como "Brentwood, Califórnia" podemser distinguidas através do uso de múltiplos tipos de fontes de nome de localidade.

Brentwood, Califórnia é tanto um local administrativo oficial próximo a San Francisco, comotambém uma vizinhança famosa porém não oficial de Los Angeles que é um nome postalpermissível porém não preferido. A Figura 4 mostra as duas localidades Brentwood naCalifórnia. Os dois locais contêm endereços que são prevalentes para fins de navegação euma boa aplicação de navegação distinguirá entre os mesmos para o usuário:

Entrar estado -> Califórnia

Entrar cidade -> Brentwood

Por favor escolher entre ->

Brentwood (cidade próximo a San Francisco)

Brentwood (vizinhança de Los Angeles)

Utilizando esse mesmo exemplo de caso de uso, em outras modalidades, se ousuário entrar o estado, cidade e nome de rua antes da aplicação processar as entradas deusuário, a aplicação pode determinar o Brentwood correto. Por exemplo:

Entrar estado -> Califórnia

Entrar cidade -> Brentwood

Entrar nome de rua -> Concord Avenue

Entrar número de rua -> 767

Encontrado: "767 Concord Avenue, Brentwood (cidade próximo a SanFrancisco), Califórnia"

Em modalidades, em um exemplo de caso de uso adicional como ilustrado naFigura 5, pequenas aldeias que podem ser listadas em fontes oficiais porém que não têmfronteiras claramente delineadas, como "Quechee, Vermont" são necessárias para inclusãoem um índice de localidade abrangente. A aldeia de Quechee, Vermont é um destinoturístico de cidade pequena popular. Simon Pierce Glassblowing pode ser encontrado nasPáginas amarelas como 1760 Quechee Main Street, Quechee, Vermont 05059. Quechee,entretanto, não é uma localidade administrativa, nem o Serviço Postal dos Estados Unidosreconhece esse endereço. O código postal 05059 é um código ZIP de "Caixa de correiosapenas" que contém muito poucos endereços de rua. Desse modo, Quechee Main Streetnão é uma rua reconhecida em Quechee. A área em volta do centro de Quechee éconhecida como White River Junction e Hartford. A Figura 5 ilustra um mapa futuro deQuechee com um limite de aldeia delineado possível. Uma boa aplicação de navegaçãonecessita reconhecer endereços como são publicados em catálogos de Páginas Amarelas,quer sejam endereços postais legítimos ou lugares incorporados ou não:Entrar estado -> Vermont

Entrar cidade -> Quechee

Entrar rua -> Quechee Main street

Entrar número -> 1760

Encontrado: "1760 Quechee Main Street, White River Junction, Vermont"Infelizmente, o nome de localidade Quechee não pode ser ligado ao endereço derua porque o limite de Quechee não é conhecido. Em vez disso, White River Junction é alocalidade designada para o endereço de rua. Essa opção está de acordo com os endereçosPostais. Uma aplicação de navegação pode determinar que encontrou a localizaçãodesejada através do uso do índice de localidade, criado como discutido abaixo. EmboraQuechee não seja a localidade para "1760 Quechee Main Street", o índice de localidadepode expandir a localidade Quechee para localizar a rua em White River Junction, Vermont.Uma aplicação de navegação pode pedir a confirmação do usuário quando a localidadecasada difere da entrada de usuário. Embora somente uma rua tenha sido encontrada,poderia ser somente um casamento possível, que o usuário da aplicação de navegaçãopode aceitar ou recusar. Aperfeiçoamentos em mapas poderiam tornar a resposta corretapossível no futuro com a adição da fronteira de Quechee. Nesse caso, o nome da localidadena qual "1760 Quechee Main Street" está localizado será na realidade Quechee.

Em modalidades, em um exemplo de caso de uso adicional como ilustrado naFigura 6, vizinhanças, que são nomes de localidade não oficiais, como "Greenwich Village"na Cidade de Nova York, são necessários para inclusão em um índice de localidadeabrangente. Há vários nomes de localidade nos Estados Unidos que são importantes paranavegação, ainda não publicados em qualquer fonte postal ou administrativa. Uma classe detais nomes são vizinhanças famosas. Os exemplos incluem Greenwich Village e SoHO naCidade de Nova York e Haight-Ashbury em San Francisco. Esses lugares são grandes obastante para conter segmentos de rua, endereços, firmas e outros pontos de interesse.Boas aplicações de navegação incluirão a capacidade de localizar lugares famosos e osendereços de rua nos mesmos, quer os mesmos sejam nomes postais ou administrativosoficiais ou não.

Sem nomes de várias fontes:

Entrar estado -> Nova York

Entrar cidade -> Greenwich Village

Cidade não encontrada : "Greenwich village"Com nomes de várias fontes:

Entrar estado -> Nova York

Entrar cidade -> Greenwich Village //nem nome postal nem administrativo

Entrar rua -> // o usuário continua por entrar o nome da ruaNesse exemplo de caso de uso, o uso de nomes de várias fontes, um mapaaperfeiçoado poderia incluir o limite de Greenwich Village. A Figura 6 mostra que oGreenwich Village pode ser definido como a área de Manhattan limitada por Spring e 14thStreets, entre Greenwich St. E Broadway. Utilizando um mapa com essas informações, odiálogo continuaria:

Entrar rua -> Carmine Street

Entrar número de rua -> 13

Encontrado: "13 Carmine Street, Greenwich Village, Nova York"Em modalidades, em um exemplo de caso de uso adicional como ilustrado naFigura 7, aldeias localizadas em uma circunscrição, como "Forest Hills" na circunscrição deQueens na cidade de Nova York, são necessárias para inclusão em um índice de localidadeabrangente. Nomes de localidade a partir de diferentes fontes podem ser utilizados paradeterminar quais das circunscrições da cidade de Nova York um nome de rua pode serlocalizado. A cidade de Nova York é composta de cinco circunscrições. Todos exceto umdeles, Queens, é independente como um nome de localidade. Em Queens, entretanto, dezdas localidades contidas são definidas. Ao procurar um endereço em Queens, o usuário nãonecessita saber a localidade em Queens na qual o endereço está localizado. O índice delocalidade, discutido abaixo, pode determinar qual aldeia contem o endereço, se o endereçoé exclusivamente contido somente em uma aldeia:

Entrar estado -> Nova York

Entrar cidade -> Queens

Entrar rua -> 70th Rd.

Entrar número de rua -> 10700

Encontrado: "10700 70* Road, Forest Hills, Nova York"

Para esse exemplo de caso de uso, o índice de localidade pode também manejarsolicitações para os nomes de aldeias localizadas em Queens:

Entrar estado -> Nova York

Entrar cidade -> Forest Hills

Entrar rua -> 70th Rd

Entrar número de rua -> 10700

Encontrado: "10700 70th Road, Forest Hills, Nova York"

As Figuras 8A e 8B mostram uma modalidade de um fluxograma de processo paraligar localidades com características geográficas em um banco de dados geográfico,tokenização, normalização, otimização e casamento de nomes de localidade e criação deum índice de localidades ordenadas por prioridade. Em modalidades, os exemplos decaracterísticas geográficas que podem ser encontradas em uma localidade incluem porémnão são limitadas a ruas, segmentos de rua, margens de segmento de rua, faces de bloco,marcos, parques estaduais, rodovias, linhas de ferry, rotas de ônibus, centros dedistribuição, locais comerciais e locais residenciais. Um segmento de rua é uma porção deuma rua, uma gama de endereços ou um endereço único. Uma margem de segmento derua é um lado de rua de um segmento de rua. Uma face de bloco é uma de quatro faces queconstituem um bloco de cidade.

Para um dado conjunto de fontes de nomes de localidade a partir de cima e paraum dado banco de dados geográfico de propriedade, o processo começa na etapa 805. Seoutro nome de localidade existir para processar na etapa 810, na etapa 815, o processodetermina se o casamento de mapa é possível se a fonte contém características geográficasque casam com aquelas no banco de dados geográficos. Se na etapa 815, o casamento demapa para a fonte for considerado como possível, na etapa 820, o casamento de mapaassocia diretamente nomes de localidade a partir da fonte de nome de localidade comcaracterísticas geográficas no banco de dados geográfico. A associação direta pode serexecutada automaticamente através de fusão, ou casamento de atributos ou manualmentepor inspeção. A associação direta é tipicamente utilizada para fontes de nome de localidadeque compartilham atributos com o banco de dados geográficos. Na modalidade preferida,fusão pode ser utilizado quando a fonte de nomes de localidade tem informações espaciaisligadas a ela indicando sua localização e extensão na terra. A associação direta é feita porsobreposição de localidades a partir da fonte de nomes de localidade espacialmente nobanco de dados geográfico, atribuição de uma localidade a quaisquer características debanco de dados geográfico que ocorrem no limite daquela localidade. O casamento deatributos é executado por casamento de atributos comuns entre uma fonte e o banco dedados geográfico, que permite então que uma associação direta seja feita. Atributos quepodem ser casados são aqueles que podem ser representados por strings ou números. Aassociação indireta é tipicamente utilizada para as outras fontes.

Em modalidades, na etapa 820 quando as fontes de nomes de localidadecompartilham atributos com o banco de dados geográficos, uma associação direta com ascaracterísticas geográficas no banco de dados geográficos é feita por casamento deatributos na fonte contra os mesmos atributos no mapa ou banco de dados geográficos. Porexemplo, o casamento de faixa pode ser utilizado para casar atributos de endereços entreuma fonte de localidade e o banco de dados geográficos. O casamento de faixa pode serfeito utilizando qualquer fonte que tenha nomes de localidade associadas a detalhe de rua,incluindo TIGER1 e o diretório de Nomes de Lugar de Cidade USPS. Os códigos deSubdivisão de condado (entidade "M") e Lugar incorporado (entidade "P") são diretamentepropagados a partir das características geográficas TIGER casadas sobre as característicasgeográfica no mapa ou banco de dados de interesse. O casamento de faixa toma um nomede rua, faixa de números de casa, e localidade a partir de TIGER e tenta casar esses itenscom um segmento de rua correspondente no banco de dados geográficos de propriedade,de interesse. Em TIGER, cada lado de um bloco de rua não somente tem faixa de endereço,tem tags que representam o tipo de entidade P (nome de lugar incorporado) naquelalocalização, o tipo de entidade M (nome de subdivisão de condado) naquela localização, umcódigo de estado, um código de bloco, um código de tratado, bem como Minor Civil Division(MCD). As faixas que casam tornam possível transferir informações a partir de TIGER sobreo banco de dados geográficos. Um casamento de faixa pode ser um casamento exato desegmentos de rua, segmentos de rua que tocam ou são exatamente alinhados ousegmentos de rua que parcialmente sobrepõem.

Na etapa 820, onde o Arquivo Estado/cidade de USPS é a fonte de nomes delocalidade, as faixas de endereços de entrega do catálogo ZIP+4 do USPS da fonte sãogeocodificados contra o mapa ou banco de dados. Em modalidades, códigos ZIP a partirdessa fonte são tratados como os próprios nomes de localidades. Códigos ZIP a partirdessa fonte também apontam para o conjunto apropriado de nomes de localidade noarquivo Estado/cidade. Para cada casamento bem sucedido, o código ZIP de cinco dígitos eum código plus4 de quatro dígitos a partir do ZIP+4 é tratado como um nome de localidade esão propagados sobre a característica geográfica correspondente.

Na etapa 825, para características geográficas em um banco de dados geográficoque não foram casadas com a fonte de nomes de localidade, a votação de face é utilizadapara casar as características geográficas com outras características no banco de dadosgeográfico, desse modo herdando atribuições de localidade a partir das característicascasadas. A Figura 9 ilustra um exemplo de votação de face utilizada para determinar umnome para uma face de bloco de cidade no banco de dados geográfico associado a umnome de localidade desconhecido. Em modalidades, furos ou características geográficasnão casadas na cobertura para as fontes de nomes TIGER são eliminados por um processode "votação de face". Para um bloco de cidade que tem uma face de bloco associada a umnome de cidade desconhecida, a votação de face determina um nome de cidade para a facede bloco com base nos nomes de cidades que correspondem a faces de blocos quecircundam a mesma, ou faces de bloco que conectam a face de bloco dada a si própria. AFigura 9 ilustra a votação de face para um bloco de cidade, de tal modo que para uma facede bloco dada, as faces de bloco utilizadas em votação de face são duas faces de blocosadjacentes à mesma e uma face de bloco oposta à mesma. As faces de bloco da Figura 9também podem ser visualizadas como características geográficas que são cada um lado deum segmento de rua. As faces de bloco adjacentes e opostas são examinadas emmodalidades, a localidade dominante na qual a face não atribuída está localizada édeterminada por um voto da maioria das outras faces adjacentes e opostas. Esse processopropaga códigos de Subdivisão de Condado e Lugar Incorporado e seus nomes associadossobre quaisquer características geográficas não codificadas a partir das característicasgeográficas codificadas adjacentes e opostas, que em modalidades são faces de bloco.

Por exemplo, na Figura 9, o lado norte de um segmento de rua de bloco da Rua doCentro é associado a um nome de cidade desconhecida porque é uma característicageográfica que não estava associada a nenhuma localidade na fonte de nome de localidade.As outras faces de bloco, ou o lado Leste da Primeira Rua um segmento de rua de bloco, olado Sul da Rua Principal um segmento de rua de bloco e o lado Oeste da Segunda rua umsegmento de rua de bloco, entretanto, foram encontradas como associadas a "Boston".

Como três desses três segmentos de rua para o bloco foram associados à Boston, o voto deface é três de três, e a Rua do Centro também estará associada à Boston. Se dois dessestrês segmentos de rua forem associados a uma cidade específica, o voto de face é dois detrês, e a Rua do Centro também será associada à cidade específica. No caso de umempate, onde os três segmentos de rua são individualmente associados a uma cidadediferente, então o voto de face é um de três. Uma vez que não há maioria de votos nessecaso, a Rua do Centro será associada à cidade de uma das ruas adjacentes mais próxima aela, que nesse caso é a Primeira rua ou a segunda rua.

Em modalidades, a votação de face pode ser utilizada para outras característicasgeográficas além de faces de bloco de cidade, como lados de segmento de rua ou margensde estrada. Em modalidades, a votação de face pode ser utilizada para dois ou mais outroslados de segmento de rua além do segmento de rua associado a um nome de cidadedesconhecida. Em modalidades, a votação de face também pode ser utilizada onde duas oumais das faces de bloco são associadas a nomes de cidade desconhecida. Nesse caso, amaioria de votos é tirada das faces de bloco restantes, e a maioria de votos ou um empate éencontrado e tratado como discutido acima. Em modalidades, a votação de face pode serutilizada para associar as faces de bloco com outros nomes de localidade além de cidadesou cidades pequenas. Por exemplo, nomes de localidade no Arquivo de Estado/cidade deUSPS são o código ZIP de cinco dígitos e um código de construção de quatro dígitos a partirdo arquivo ZIP+4.

Outras modalidades de votação de face incluem um voto ponderado ou um voto decomprimento linear em vez de maioria de votos. Em modalidades utilizando um votoponderado, certas faces de bloco adjacentes a uma face de bloco não associada a umalocalidade têm preferência, ou têm peso maior no processo de votação. Um voto ponderadopode ter qualquer componente de ponderação que mede a confiança das atribuições deface de bloco adjacentes. Por exemplo, preferência poderia ser dada a faces de bloco quecorresponde a ruas principais ou que são localizadas em regiões maiores. O comprimentodas faces de bloco é outra ponderação. Em modalidades, utilizando um voto decomprimento linear, para uma dada face de bloco não associada a uma localidade, paracada localidade conhecida associada a faces de bloco adjacentes à face de bloco dada, ocomprimento total das faces de bloco é tomado para determinar qual localidade associada afaces de bloco adjacentes tem faces de bloco do comprimento linear total mais longo. Essalocalidade resultante é então atribuída à face de bloco dada não associada a umalocalidade.

Na Figura 8A, se na etapa 815 o casamento de mapa não for possível porque afonte não compartilha nenhum atributo com o banco de dados geográficos, na etapa 855, ocasamento de nome de fonte cruzada é empregado em modalidades. Cruzamento de fontesé associação indireta de nomes de localidade na fonte, ou primeira fonte, com aqueles deoutra fonte já associada diretamente a características geográficas no banco de dadosgeográfico. Na etapa 855, se o casamento de nome de fonte cruzada for possível porqueuma segunda fonte já diretamente associada a características geográficas no banco dedados geográficos for encontrada com nomes de localidade em casamento com umaprimeira fonte, na etapa 860 a primeira fonte é casada com a segunda fonte. Na etapa 865,cada nome de localidade na primeira fonte herda as associações com característicasgeográficas a partir da segunda fonte, e é desse modo associado indiretamente com acaracterística geográfica específica. Em modalidades, os exemplos, de característicasgeográficas herdadas são lados de segmento de rua, faces de bloco e linhas de ferry. Emmodalidades, os dados FIPS55 são uma fonte de nomes úteis para casamento de nome decruzamento de fonte. Por exemplo, as localidades GNIS para fonte de Lugares Povoados écasada contra os nomes de localidade na fonte FIPS55 em um estado e condado. Onde oscasamentos são feitos, os nomes GNIS herdam as associações com lados de segmento derua a partir de seus nomes FIPS55 em casamento. A partir da etapa 865, o processo semove para a etapa 830, como discutido abaixo. Se na etapa 855 o casamento decruzamento de fonte não for possível para a fonte, a fonte não é utilizável no processo, e oprocesso retorna para selecionar outra fonte de localidade na etapa 810.

Os nomes de localidade tirados das várias fontes de nomes de localidade sãotokenizados, normalizados, otimizados e/ou casados, fundidos ou adornados para eliminarnomes de localidade duplicatas e variantes, em modalidades. Na modalidade preferida,todas as etapas de tokenização, normalização, otimização, casamento e fusão ou adornosão executadas. Esse processo reduz o número de nomes de localidade para cadalocalidade que tem dois ou mais nomes similares, enquanto também preserva nomes delocalidade que são significativamente diferentes. Essas etapas acomodam diferenças emcodificação de nome entre as várias fontes. Um exemplo de nomes de localidade similares apartir de várias fontes é a cidade de HO-Ho-Kus, Nova Jérsei, que aparece como a seguirem várias fontes de nomes de localidade:

TIGER registro tipo C: Ho-Ho-Kus TwnshpEstado/cidade de USPS: HO HO KUS Township

Centro de assentamento POI: HO-HO-KUS

FIPS55-3: Ho-Ho-Kus (Hohokus)

GNIS: Ho-Ho-Kus

A partir das etapas 825 e 865 na Figura 8A, o processo se move para a etapa 830.Na etapa 830, a primeira parte do processo de casamento de nomes, tokenização, ouanálise pode dividir um nome de localidade em tantos quanto aproximadamente dez tokensou componentes, em modalidades. Muitas técnicas podem ser utilizadas para tokenizarnomes de localidade. A finalidade dessa etapa é dividir o componente ou porção significativado nome de localidade, ou o "corpo" do nome, para fins de indexação. Os outroscomponentes, como prefixos ou sufixos serão individualmente componentes separados.Nomes de localidade são então representados por tokens em um índice, desse modopermitindo que o desenvolvedor de aplicações indexe a porção significativa do nome. Porexemplo, tanto Amherst como South Amherst será então indexado sob "A" se desejado. Aeliminação de duplicatas em modalidades permitirá que os usuários finais tenham acesso amais nomes em aplicações de memória limitada e evitará confusão para o usuário de ver omesmo nome apresentado múltiplas vezes.

A tokenização de nomes de localidade a partir das duas primeiras fontes de nomede localidade listadas acima para o exemplo de Ho-Ho-Kus, Nova Jérsei produz osseguintes tokens de sufixo e corpo:

Corpo: Ho-Ho-Kus, sufixo: Twnshp

Corpo: HO HO KUS, sufixo: Township

A tokenização é útil para isolar aqueles componentes que definem um nomeexclusivo e por associação, aqueles tokens que podem ser ignorados no processo decasamento. A maioria dos usuários finais desejará que "Rutland" case com "RutlandTownship", isto é, que o termo "Township" seja tratado como insignificante. Ao mesmotempo, a maioria dos usuários finais desejará que "Boston" não case com "South Boston",isto é, o termo "South" seja tratado como significante. Outro motivo para tokenização éoferecer a um desenvolvedor de aplicações de software, flexibilidade em apresentar nomesde localidade para o usuário final porque a porção significativa do nome será indexada. Porexemplo, por tokenização "Hollywood" e "West Hollywood", ambos serão apresentadoscomo opções de seleção a um usuário final que entra uma busca de mapa para "Hollywood."Isso ocorre porque o token de "Corpo" para os dois será "Hollywood", visto que WestHollywood será tokenizado como Corpo: Hollywood, Prefixo: West, e Hollywood serátokenizado como Corpo: Hollywood.

Em outra modalidade, a tokenização ajuda a determinar a expansão correta deabreviaturas sensíveis a contexto. Por exemplo, um token de prefixo de localidade "St." maisprovavelmente se refere a "Saint", ao passo que um token de sufixo de localidade "St." maisprovavelmente se refere a "Estado".

O que se segue são outros tipos de tokens e exemplos desses tokens:

Pré-direção - direção dianteira ("North" Adams)

Pré-tipo - tipo dianteiro ("Lake" Isabella)

Prefixo - dianteira, porém não uma direção ou tipo ("Old" Orchard Beach)).

PreNome - palavras que não são tipo antes do corpo (Lake "of the" woods)

Corpo - peça principal utilizada para fins de índice (Lake "Isabella")

Tipo posterior - tipo traseiro (Imperial "Beach")

Direção posterior - token de direção traseira (Leisure Village "West")

Sufixo - traseira, porém não uma direção ou tipo (Manchester "By the sea")

Divisão - identificador numérico especificando divisões da localidade(Meredosia "1")

Adorno - informação suplementar parentética, como nome de condado paraesclarecer a localização de um nome de localidade (Middletown "(Bethlehem)").

Na etapa 835 da Figura 8A, a normalização de tokens a partir da etapa detokenização envolve genericamente um ou mais dos seguintes processos: expandirabreviaturas, reduzir ou remover pontuação, utilizar caso compatível (maiúscula ouminúscula) e remover espaços embutidos, em modalidades. Em modalidades, asabreviaturas padrão para direcionais e para tipos são expandidas. Por exemplo, aabreviatura direcional "N" é expandida para "North". Para abreviaturas de tipo, por exemplo,"Mt." É expandida para "Mount" e "AFB" é expandida para "Air Force Base." Dado quenomes que aparecem em fontes diferentes podem ser representados de forma diferente, anormalização adequada de abreviaturas é crítica para o processo de casamento. Emmodalidades, espaços incorporados e pontuação são removidos. Em modalidades, escritaem letra maiúscula pode ser normalizada utilizando letra maiúscula ou letra minúsculaconsistente para os tokens de nome de localidade. A escrita em letra maiúscula tambémpode ser normalizada por escrever em letra maiúscula somente a primeira letra de cadatoken, em modalidades. Além disso, diferenças de escrita em letra maiúscula podem seracomodadas no processo de casamento em vez de no processo de normalização, emmodalidades. Na modalidade preferida, a escrita em letra maiúscula é normalizada paraletra maiúscula consistente. Utilizando o exemplo de Ho-Ho-Kus, Nova Jérsei, anormalização dos tokens produz os seguintes resultados:

Corpo: HOHOKUS, sufixo: TOWNSHIP

Corpo: HOHOKUS, sufixo: TOWNSHIP

O seguinte exemplo de caso de uso ilustra os benefícios das características detokenização e normalização que podem ser armazenadas no índice de localidade, cujacriação é discutida abaixo. Sem essas características no índice, várias abreviaturasaparecem como nomes de cidades diferentes. Com essas características no índice, asabreviaturas são colocadas em uma forma comum, permitindo que o desenvolvedor deaplicações dobre a lista em uma única entrada não ambígua. Embora a escrita em letramaiúscula de tokens seja normalizada em letra maiúscula consistente para facilitarcasamento, tokens são tipicamente apresentados ao usuário somente com a primeira letrade cada token maiúscula.

Sem nomes de localidade tokenizados e normalizados no índice:

Entrar cidade -> Randolph

Por favor escolher entre ->

Randolph Hghts

Randolph Heights

Randolf Hts

Com nomes de localidade tokenizados e normalizados no índice:

Entrar cidade -> Randolph

Você escolheu: Randolph Heights

O seguinte exemplo de caso de uso ilustra os benefícios de tokenização enormalização de tokens direcionais em nomes de localidade. Por identificar tokensdirecionais, nomes de localidade podem ser indexados por seu corpo, em vez de pordireção. Após direcionais serem normalizados, um desenvolvedor de aplicações necessitasomente checar em relação a tokens normalizados porém não quaisquer abreviaturasdesses tokens.

Sem nomes de localidade tokenizados e normalizados no índice:

Entrar cidade -> Boston

Encontrado: Boston

Entrar cidade -> South B

Por favor escolher entre ->

South Bank

South Barrister

South Barnstable

South Boston

Entrar cidade -> S. Boston

Cidade não encontrada: "S. Boston"

Entrar cidade -> South Boston

Encontrado: "South Boston"

Com nomes de localidade tokenizados e normalizados no índice:

Entrar cidade -> BostonPor favor escolher entre ->

Boston

South Boston

Na etapa 840 da Figura 8A, a otimização para dois ou mais nomes de localidadesimilares a partir da etapa de normalização associa genericamente cada nome de localidadesimilar com características geográficas contidas na localidade, em modalidades. Osexemplos de características geográficas incluem ruas, segmentos de rua, marcos, parquesestaduais, rodovias, locais comerciais e locais residenciais. No exemplo de Ho-Ho-Ku, NovaJérsei, a otimização encontrará as mesmas características geográficas para HoHokus epara HOHOKUS.

Na etapa 845 da Figura 8A, em uma máscara de fonte principal, o bit seguinte namáscara de fonte é alocado à fonte. Em modalidades, a máscara é exclusiva em um país.Em outras modalidades, a máscara poderia ser exclusiva para qualquer área geográfica,como um estado ou continente. A Figura 10 mostra dois exemplos de máscaras de fonte denome de localidade para os Estados Unidos e para o Canadá. Em modalidades, cadaposição de bit na máscara de fonte representa uma única fonte de nome de localidade. Amáscara pode conter uma ou mais fontes de nome de localidade administrativa, postal ououtra. A máscara é exclusiva em um país e não envolve prioridade de fontes de nome delocalidade. Para cada valor de bit na coluna "Valor de bit decimal", uma fonte de nome delocalidade na coluna "Fonte de nome de localidade" é alocada ao valor de bit. Para fins deindexação, a máscara de fonte de localidade permite a flexibilidade para definir tiposdiferentes de nomes de localidade para se adequar melhor à aplicação final. Emmodalidades, as fontes na máscara indicada como "Trump" podem ser utilizadas para darprioridade máxima a nomes de localidade que são encontrados nessas fontes para fins deindexação. Para cada nome de localidade na fonte, uma máscara de fonte individualtambém é criada, mostrando as fontes nas quais o nome de localidade aparece.

Na etapa 850, a posição de bit seguinte na máscara de fonte para cada nome delocalidade na fonte é definida para essa fonte. Nomes que aparecem em múltiplas fontesterão bits definidos na máscara para cada fonte na qual aparecem. Por exemplo, o nome"Boston" é simultaneamente um nome de subdivisão de condado, um lugar administrativo eo nome postal preferido para diversos códigos ZIP. Nomes que não aparecem em múltiplasfontes terão somente um único conjunto de bits em sua máscara correspondendo a suafonte. O processo retorna para a etapa 810 para processar a próxima fonte de nomes delocalidade se existir uma.

Se na etapa 810 da Figura 8A não houver fontes de localidade restantes paraprocessar, o processo se move para a etapa 868 na Figura 8B. Na etapa 868, os nomesotimizados a partir de todas as fontes utilizáveis são casados. As fontes utilizáveis sãoaquelas para as quais o casamento de mapa foi possível na etapa 815 e aquelas fontespara as quais outro casamento de fonte foi possível na etapa 855 na Figura 8A. Ocasamento concatena os tokens normalizados em nomes completos e compara os mesmospara determinar se podem ser considerados um casamento, em modalidades. Emmodalidades, a normalização de caso de nome de localidade ou diferenças de escrita emletra maiúscula poderia ser executada nessa etapa de casamento de nome em vez da etapade normalização acima. Em modalidades, a lógica de casamento insensível o caso poderiaser utilizada nessa etapa de casamento. Para cada estado nos Estados Unidos, todos osnomes de localidades a partir das fontes designadas são casados em modalidades.

Muitos algoritmos diferentes são possíveis para casamento de nome. Os exemplosde técnicas de casamento de nome incluem casamento sensível a contexto, casamentofonético e Soundex. O casamento sensível a contexto é casamento string dos nomes oucasamento da soletração de nomes. Esse tipo de casamento é executado comconhecimento de quais tokens estão sendo casados que permitem regras especiais. Porexemplo, no token de corpo, um bom algoritmo de casamento sensível a contexto podecasar "John F. Kennedy" e "John Fitzgerald Kennedy". Um excelente algoritmo decasamento sensível a contexto pode casar "MLK" e "Martin Luther King." O casamentofonético, por outro lado, casa os sons de palavras ao contrário da soletração das palavras.Por exemplo, "fish" e "phish" casam foneticamente. Para casamento de nome em váriosidiomas, diferentes algoritmos de casamento fonético podem ser utilizados. Soundex é umalgoritmo fonético para indexar nomes por seu som quando pronunciado em inglês. Oobjetivo básico é para nomes com a mesma pronúncia serem codificados na mesma stringde modo que o casamento possa ocorrer apesar de diferenças pequenas em soletração.Informações mais detalhadas em relação a algoritmos fonéticos podem ser encontradas nopedido número 11/377.764, depositado em 16 de março de 2006, intitulado "GeographicFeature Name reduction using phonetic algorithms" de Jesse Sheridan.

Em modalidades, para que dois nomes completos casem, as strings devem casarexatamente. Se nomes completos não casarem, em modalidades, um casamento de tokensde corpo é tentado. Tokens de corpo devem casar e tokens de direção e tipo tambémdevem casar para um casamento de token bem sucedido. Desse modo, o casamento dostokens pode não iniciar com um ou ambos tokens dianteiros, e um token deve ser umasubstring dianteira da outra. Desse modo, o casamento de tokens também deve ignorarcertos tokens. Em modalidades, variações de soletração pequenas podem ser permitidasentre dois nomes em casamento. Em modalidades, o casamento de nome é implementadorelativamente de forma conservativa para evitar casamentos falsos. Desse modo:

"North Boston" não casa com "South Boston"

"South Boston" não casa com "Boston""Township of Rutland" não casa com "Rutland Township"Na etapa 870 da Figura 8B, todos os conjuntos de nomes de localidade casadosencontrados na etapa 868 são processados. Cada conjunto de nomes de localidadecasados são localidades tendo nomes duplicatas ou levemente variantes. Na etapa 870, seoutro conjunto de nomes de localidade casados existir, o processo determina se nomescasados representam geometria de sobreposição na etapa 872. Na etapa 872, nomescasados representam geometria de sobreposição se as localidades se sobrepõem oumesmo se são somente adjacentes entre si, desde que compartilhem pelo menos umacaracterística geográfica em comum determinada na etapa de otimização 840.

Se na etapa 872 da Figura 8B, os nomes casados representarem geometria desobreposição, se na etapa 873, a geometria de sobreposição for exata, então na etapa 874,nomes duplicatas exceto um são eliminados a partir das entradas de índice de localidade nobanco de dados geográficos. Se todas as características geográficas associadas a um nomede localidade forem iguais àqueles de outro, esses nomes de localidade são duplicatasverdadeiras e todos exceto um são eliminados. Nomes de localidade são eliminados se esomente se os nomes representarem a mesma localidade. Essa etapa elimina localidadesduplicatas e reduz o conjunto de nomes de localidade. Para um índice de localidade tendomuitas entradas duplicatas, essa técnica reduzirá muito a quantidade de indexação eespaço exigido pelo índice. No exemplo de Ho-Ho-Kus, Nova jérsei, os tokens normalizadosconcatenados juntos para cada nome são ambos "HOHOKUS TOWNSHIP". Como essesdois nomes de localidade serão determinados como tendo todas as característicasgeográficas em comum a partir da etapa de otimização, esses nomes de localidades sãoduplicatas verdadeiras e um é eliminado. O processo então retorna para a etapa 870 paradeterminar se outro conjunto de nomes de localidade casados existe.

Se na etapa 873 da Figura 8B a geometria de sobreposição não for exata, ou umalocalidade compartilhar pelo menos um porém um número menor do que todas ascaracterísticas geográficas com outra localidade, normalmente uma localidade com umnome levemente diferente, essas localidades são consideradas como sendo a mesmalocalidade e são fundidas na etapa 875. Por exemplo, "Randolph" e "Randolph Center" emVermont são duas cidades separadas porém sobrepostas. Como as duas cidades sesobrepõem, compartilham pelo menos uma característica geográfica em comum, sãoconsideradas como sendo a mesma localidade e são fundidas.

Em modalidades, a fusão de nomes de localidade somente ocorre quando aslocalidades de sobreposição não têm características de não sobreposição que não podemser distinguidas entre si. Por exemplo, se Randolph e Randolph Center tiverem ambas umaMain Street sem números de rua em sobreposição, as duas cidades podem ser fundidas. Seas duas cidades tiverem um "2 Main Street" por exemplo, entretanto, as cidades não devemser fundidas.

O seguinte exemplo de caso de uso ilustra a vantagem de eliminar todos exceto umdos nomes de localidade duplicatas a partir de múltiplas fontes que têm geometria desobreposição. Sem essa característica, um nome de localidade é listado múltiplo em opçõesapresentadas ao usuário.

Sem eliminar duplicatas:

Entrar cidade -> Hanover

Por favor escolher entre ->

Hanover (subdivisão de condado)

Hanover (lugar administrativo)

Hanover(03755)

Após eliminar duplicatas:

Entrar cidade -> Hanover

Encontrado: "Hanover"

O seguinte exemplo de caso de uso também ilustra a vantagem de fundirlocalidades tendo nomes levemente diferentes. Sem fusão, o usuário pode não saber qualnome levemente diferente é a localidade na qual um destino desejado está localizado. Coma fusão, o usuário não necessita distinguir entre nomes. Por exemplo, as localidades"Randolph", "Randolph Center" e "Randolf Township" se sobrepõem, e desse modo sãofundidos em uma área comum, representada pelo nome único "Randolph". Desse modopara uma busca de usuário:

Sem fusão:

Entrar cidade -> Randolph

Entrar rua -> Main Street

Por favor escolher entre ->

Main Street, Randolph

Main Street, Randolph Center

Main Street, Randolph Township

Com a fusão:

Entrar cidade -> Randolph

Entrar rua -> Main Street

Encontrado: "Main Street, Randolph"

Na etapa 876 da Figura 8B, uma união de todas as características a partir dosnomes casados é atribuída ao nome fundido.Por exemplo, em FIPS55, a Subdivisão deCondado de Boston define certa geografia. O Lugar Administrativo de Boston define outrageografia que sobrepõe porém não é necessariamente igual. O lugar postal de Bostondefine um terceiro conjunto de geografia cobrindo ruas nas quais a correspondência norte-americana pode ser entregue. A criação de uma união dessas características diferentesforma um conjunto completo de características que são associadas à Boston. A união dascaracterísticas geográficas associadas a cada um desses nomes relacionados à Bostoncompreende um conjunto das características geográficas incluindo cada uma dessas fontes.

Por exemplo, se Adams St. For de interesse para um usuário final, embora Adams St. nãofaça parte do lugar postal Boston, Adams St. será encontrado para o usuário porque fazparte da Subdivisão do Condado de Boston devido à união de características geográficas apartir do casamento de nomes de localidade de várias fontes de nomes de localidade.Desse modo, uma lista de nomes de localidade exclusivos resulta, com conjunto de bits em uma máscara de fonte correspondendo às fontes nas quais cada nome é encontrado, e umaunião de todas as características geográficas às quais cada nome se aplica. O processoentão retorna para a etapa 870 para determinar se outro conjunto de nomes de localidadecasados existe.

A Figura 11 mostra uma modalidade de um algoritmo para reduzir o conjunto de nomes de localidade através do casamento de nomes de localidade. Para cada nome delocalidade A em uma fonte de nomes de localidade, para cada nome B em quaisquer outrasfontes que casam com o nome A, atribuir a A quaisquer lados de rua de segmentoassociados a B ainda não atribuídos a A. Essa é a etapa 876 da Figura 8B acima. Incluirquaisquer bits na máscara de fonte B não incluídos ainda na máscara de fonte A e deletar B. Na etapa 872 da Figura 8B, se os nomes casados não representarem geometria desobreposição, os nomes casados são adornados para tornar os mesmos distintos na etapa878. Os nomes casados que não representam geometria de sobreposição são localidadestendo nomes duplicatas ou levemente variantes que são fisicamente separadas. Emmodalidades, essas localidades fisicamente separadas são cidades com nomes iguais ou levemente diferentes. Genericamente, tais localidades com nomes duplicatas existem emdiferentes condados em um estado. Desse modo, esses nomes duplicatas podem serdistinguidos para um usuário mostrando um adorno, por exemplo o nome de condado noqual a localidade está localizada. Um adorno de localidade é tipicamente mostrado emparênteses ou em aspas próximo ao nome de localidade. Nomes de condado ou outros adornos de borda, entretanto, podem não ser reconhecíveis para os usuários não locais. Emvez disso, os nomes de cidades grandes, facilmente reconhecíveis próximo a cadalocalidade tendo nomes duplicatas fornecerão melhores informações para o usuário. Dessemodo, na etapa 878, um adorno de cidade separado é armazenado no índice de localidadepara cada um dos nomes a partir da etapa 872. Informações mais detalhadas em relação à criação desse tipo de adorno podem ser encontradas no pedido número 11/345.877,depositado em 1o de fevereiro de 2006, intitulado "Method for differentiating duplicate orsimilarly named disjoint Iocalities within a state or other principie geographic unit of interest",de Michael Geilich. O processo então retorna para a etapa 870 para determinar se outroconjunto de nomes de localidade casados existe.

O seguinte exemplo de caso de uso mostra adornos para localidades separadastendo nomes duplicatas ou levemente variantes:

Adornar com nomes de condado:

Entrar estado -> PAEntrar cidade -> BethelPor favor escolher entre ->Bethel (Berks)BetheI(AIIegheny)Bethel (Lancaster)Bethel (Mercer)Bethel (SuIIivan)Bethel (Wayne)

Adornar com nomes de cidades grandes, próximas, facilmente reconhecíveis:

Entrar estado -> PAEntrar cidade -> Bethel

Por favor escolher entre ->

Bethel (Fredericksburg)Bethel (Pittsburgh)Bethel (Lancaster)Bethel (Youngstown)Bethel (WiIIiamsport)Bethel (Scranton)

Nesse exemplo de caso de uso, a aplicação processa cada entrada de usuárioantes de solicitar mais informações a partir do usuário. Em outras modalidades, para"Adornar com nomes de cidades grandes, próximas, facilmente reconhecíveis" se o usuárioentrar o estado, cidade e nome de rua antes da aplicação processar essas três entradas deusuário, um destino único pode ser determinado se o endereço de rua for encontradosomente em uma das opções. Por exemplo:

Adornar com nomes de cidades grandes, próximas, facilmente reconhecíveis:

Entrar estado -> PAEntrar cidade -> BethelEntrar nome de rua -> Main StreetEncontrado: 'Main Street, bethel (Fredericksburg)"

Se na etapa 870, outro conjunto de nomes de localidade casados não existir, entãona etapa 880 da Figura 8B, o índice é criado. O índice é primeiramente ordenado porcaracterística geográfica. Para cada característica geográfica, localidades que contêm acaracterística geográfica são indexados em ordem de prioridade. Nomes de localidade noíndice são ordenados por prioridade para permitir que desenvolvedores de aplicaçõesprogramem seleção dos nomes mais prevalentes para qualquer característica geográficanas aplicações. Isso provê aos usuários finais os nomes mais prevalentes a partir dos quaisselecionar por exemplo, em ambientes de memória limitada. Para um dispositivo dememória limitada que pode armazenar somente alguns nomes de localidade para cadacaracterística geográfica, um desenvolvedor de aplicações pode utilizar o índice delocalidade para escolher as localidades com prioridade mais elevada para o usuário parauma característica geográfica associada a mais de algumas localidades. Similarmente, paraaplicações de busca bottom-up, a aplicação solicita o endereço, ou característica geográfica,a partir do usuário e apresenta uma lista de localidades a partir da qual o usuário escolhe.Ao apresentar a lista de localidades, os nomes com prioridade mais elevada associados aoendereço podem ser utilizados.

Em modalidades, ordem de prioridade das localidades associadas a umacaracterística geográfica se baseia na prevalência de cada nome de localidade em usocomum para uma aplicação pretendida. Em modalidades, a priorização com base em usocomum permite que nomes de localidade sejam ordenados de forma diferente para usuáriosdiferentes. No exemplo de localidades de sobreposição como "Cidade de Nova York","Manhattan" e "SoHo", em uso comum, um usuário local conheceria bem a área, maisprovavelmente usaria a mais específica das três localidades, ou "SoHo". Se uma aplicaçãofor destinada a esse usuário local, o nome de localidade de prioridade mais elevada seriamais provavelmente um tendo o número mínimo de fontes no qual o nome de localidadepode ser encontrado. Desse modo, a ordem de prioridade a partir do mais elevado para omais baixo seria "SoHo", "Manhattan" a seguir "Cidade de Nova York."

Utilizando o mesmo exemplo de localidades em sobreposição na cidade de NovaYork, em uso comum, um usuário não local não conhece bem a área local, entretanto, maisprovavelmente utilizaria a localidade mais conhecida, facilmente reconhecível. Se umaaplicação for destinada a esse usuário não local, o nome de localidade de prioridade maiselevada mais provavelmente seria um tendo o maior número de fontes no qual o nome delocalidade pode ser encontrado. Desse modo, a ordem de prioridade a partir do maiselevado para o mais baixo seria "Cidade de Nova York", "Manhattan", então "SoHo".

Em modalidades, algoritmos para determinar ordem de prioridade em umaaplicação podem ser aplicados diferentemente para atender usos comuns diferentes paraum usuário. Por exemplo, para um usuário local navegando em uma localidade como umacidade grande, o usuário poderia querer uma prioridade de nomes de localidade com baseem uso comum para um usuário local. Enquanto o mesmo usuário que navega para amesma cidade grande de longe, entretanto, o usuário pode querer uma prioridade diferentecom base em uso comum para um usuário não local. Após o usuário chegar na cidadegrande e cruzar o limite para dentro da cidade, entretanto o usuário pode querer que aprioridade mude de volta para aquela de um usuário local.

Muitos esquemas de ordenação de prioridade diferentes são possíveis. Namodalidade preferida, a localidade de prioridade mais elevada associada a umacaracterística geográfica é aquela encontrada em uma fonte de nome postal preferida, entãoa prioridade das localidades restantes é determinada pelo número de conjuntos de bits emcada máscara de fonte de localidade. Em modalidades, uma primeira localidade tem umaprioridade mais elevada do que a segunda localidade se a primeira localidade for mais bemconhecida ou prevalente em uso comum. Em modalidades, a prioridade de um nome delocalidade é determinada pelo número de fontes no qual o nome pode ser encontrado. Onome de localidade para uma característica geográfica com a prioridade mais elevada é onome de localidade que pode ser encontrado no número maior de fontes, e desse modoque, tem o conjunto de mais bits em sua máscara de fonte. A ordem de prioridade dosnomes de localidade para uma característica geográfica é da mais elevada para a maisbaixa.

Em modalidades, um desenvolvedor de aplicações também pode utilizar a máscarade fonte para cancelar esse esquema de prioridade default por preferir certas fontes denomes de localidade em relação a outras. Em outras modalidades, a prioridade é definidaem termos do tamanho de localidade física maior ou população de localidade maior. Emoutras modalidades, prioridade é definida como o número maior de característicasgeográficas, por exemplo, segmentos de rua, em uma localidade. A prioridade pode serdefinida também em termos do número maior de características geográficas principaislocalizadas na localidade, ao contrário do número de características geográficas localizadasna localidade, em outras modalidades. Um exemplo de uma característica geográficaprincipal é uma rodovia importante. Em modalidades, a prioridade pode ser definidautilizando as máscaras de fonte de localidade para determinar uma preferência de certasfontes de nomes de localidade em relação a outras. Em modalidades, um desenvolvedor deaplicações pode utilizar nomes de localidade a partir de fontes de localidade indicadas como"Trump" na Figura 10 como os nomes de prioridade máxima.

Em modalidades, no caso de empates de prioridade de localidade, uma separaçãoprimária é executada utilizando um dos esquemas acima, e onde necessário, por umaseparação secundária com base em um dos esquemas acima. Na modalidade preferida,uma separação primária é executada no número de fontes a partir de mais elevada paramais baixa na qual cada localidade pode ser encontrada. Uma separação secundária sebaseia, por exemplo, no número de características geográficas, ou segmentos de rua, apartir da mais elevada para a mais baixa contida em cada localidade.

A Figura 12 mostra uma modalidade de um algoritmo para determinar a prioridadede nomes de localidade para uma dada característica geográfica. Para cada lado desegmento de rua S em um banco de dados geográfico, encontrar todos os nomes delocalidade A para os quais S é atribuído. Para cada A, encontrar o nome A com o conjuntode mais bits em sua máscara de fonte. Atribuir A para o nome de prioridade mais elevadaseguinte no índice para esse lado de segmento de rua S.

O processo da Figura 8B termina na etapa 890.

A Figura 13 mostra uma modalidade de arquivos de índice de localidade incluindouma tabela de Prioridade de Localidade de Característica, uma tabela de Nome deLocalidade e uma Tabela Encontrar característica. Essas tabelas são finalmentearmazenadas em um banco de dados. Em modalidades, na tabela de Prioridade deLocalidade de Característica da Figura 13, lista localidades por prioridade para cadacaracterística geográfica. Em modalidades, cada característica geográfica na tabela éassociada a um número ID de característica, FFJD. Os números de ID de característicapodem ser seqüenciais porém não têm necessariamente de ser seqüenciais. Os números deID de característica são também um link para a tabela Encontrar Característica. Emmodalidades, cada localidade associada a cada característica geográfica na tabela tambémé associada a um número de ID de localidade, NAMEJD. Os números de ID de localidadepodem ser seqüenciais porém não têm necessariamente de ser seqüenciais. O campoPRIORIDADE indica a prevalência do nome de localidade associado à característicageográfica. Como mencionado acima, muitos esquemas de prioridade existem para priorizaros nomes de localidade associados a cada característica geográfica. PRIORIDADE é umnúmero seqüencial que inicia com "1" como a prioridade mais elevada. A tabela tambémcontém a máscara de fonte de nome de localidade para essa localidade, LOC_MASK,descrito acima.

O formato variável do índice de localidade permite que qualquer número deentradas de tabela seja incluído para cada característica geográfica na tabela de Prioridadede Localidade de Característica. Isso é especialmente importante na América do Norte paranomes postais. Embora haja genericamente somente um nome de localidade postalpreferido para cada local, o serviço postal também inclui qualquer número de nomes delocalidade postal permissíveis para o mesmo local. O índice de localidade inclui todos osnomes postais preferidos e permissíveis para cada característica geográfica.

Em modalidades, a tabela de Nome de Localidade da Figura 13 é ligada à tabela dePrioridade de Localidade de Característica através dos números de ID de localidade,NAMEJD. A tabela também contém o nome completo da localidade, FULL_NAME,utilizando letras de caso misturado em modalidades. Em modalidades, os nomes delocalidade completos como representados em FIPS55 são utilizados para a codificação finalde nomes de localidade completos nessa tabela. Outras fontes para representar nomes delocalidade completos podem ser entretanto, utilizados. O campo NAME_KEY da tabela é ocomponente significativo do nome de localidade para fins de indexar. Em modalidades,NAME_KEY é encontrado a partir de tokenização e normalização do nome de localidadeacima. Isso permite que "Hollywood" e "West Hollywood" sejam ambos indexados sob "H",por exemplo, visto que o token de corpo principal para ambos é "Hollywood". O campoADORNO é um pointer para outra entrada na Tabela de Nome de Localidade contendo onome de localidade de um local ou cidade grande e facilmente reconhecível próximo dalocalidade. Em modalidades, ADORNMENT é armazenado na tabela somente quando alocalidade é uma localidade ambígua em uma subdivisão primária de um condado, como umestado. Em modalidades, o adorno é utilizado para diferenciar localidades duplicatas emuma lista em um sistema ou dispositivo de usuário.

O campo NAME_LC é um código de três caracteres para o idioma do nome delocalidade. Em modalidades, NAME_LC é definido para cada nome de localidade paraindicar o idioma nativo do nome para suportar países de múltiplos idiomas. Em modalidades,NAME_LC pode ser qualquer número de caracteres. LOC_SIZE indica uma contagem donúmero de características geográficas associadas a esse nome de localidade e pode serutilizado por desenvolvedores de aplicações para cancelar o esquema de PRIORITY defaultfornecido na tabela de prioridade de Localidade de Característica. COUNTRY é um códigode país e há uma abreviatura de três caracteres do país no qual a localidade está localizada.Em modalidades, COUNTRY pode ser um código de país padrão como ISO 3166-1, que fazparte do padrão ISO 3166 publicado pela primeira vez pelo International Organization forStandardization. Em modalidades, COUNTRY pode ser qualquer número de caracteres.CENTER_ID é um link com características de ponto de centro de cidade encontradas emoutro lugar no banco de dados geográficos para essa localidade. Em modalidades, essascaracterísticas de ponto de centro de cidade são as coordenadas de latitude e longitude deponto central de localidade, bem como um segmento de rua correspondendo ao centro decidade. Centros de cidade fornecem um ponto em uma localidade para um usuário quandoum endereço de rua específico não é solicitado ou não pode ser encontrado.

Em modalidades, a tabela de Nome de Localidade da Figura 13 pode conter muitosoutros tipos úteis de informações sobre localidades. Por exemplo, a inclusão de fonemas natabela de Nome de Localidade seria útil para aplicações de texto para fala, onde um fonemaé um conjunto de sons de fala ou elementos de sinal que são equivalentes de formacognitiva. Outros exemplos de tipos diferentes de informações que podem ser armazenadasna tabela de Nome de Localidade são uma imagem da prefeitura de uma localidade e onúmero de telefone do departamento de polícia de uma localidade.Em modalidades, a tabela Encontrar característica da Figura 13 contéminformações sobre cada característica geográfica. FFJD é um número de ID decaracterística utilizado para ligar informações de características geográficas à tabela dePrioridade de Localidade de Característica. FEAT_TYPE é o tipo de característicageográfica, como "R" para características de estrada e "F" para características de linha deferry. FEATJD é um link para informações no banco de dados geográfico sobre acaracterística como nomes de ruas e faixas de endereço. FEATJD também provê ligaçãoindireta com outro conteúdo ligado ao banco de dados geográfico como Pontos deInteresse. SIDE é o lado da característica geográfica, por exemplo, uma margem de rua.SIDE inclui "R" para o lado direito, "L" para o lado esquerdo, "B" para os dois lados e "nulo"para "não aplicável."

Em modalidades, o índice de localidade é fornecido em múltiplos formatos,incluindo formatos internacionais, para permitir integração fácil com bancos de dadosgeográficos de propriedade. O índice de localidade é fornecido para acomodar dados apartir de qualquer país. Embora o formato seja generalizado, o conteúdo é moldado paraincluir fontes de localidade específicas e tipos apropriados em cada país. Uma aplicação depropriedade provê a pronúncia para cada nome de localidade.

Em modalidades, para uso de tabela de índice de localidade, em umaimplementação top-down de encontrar um endereço, a localidade é primeiramente resolvida,e então a característica geográfica correta é encontrada na localidade. Uma aplicação denavegação executará primeiramente casamento de nome para encontrar o nome delocalidade desejado na tabela Nome de Localidade. Após encontrar a localidade, a tabelaPrioridade de Localidade de Característica é buscada utilizando o NAMEJD da localidadeescolhida para determinar as características geográficas contidas naquela localidade. OsFFJDs daquelas características são utilizados como índice na tabela EncontrarCaracterística para recuperar informações sobre essas características necessárias paraencontrar uma característica específica, como nomes de rua e faixas de endereço no casode segmentos de rua, e então o casamento é executado para selecionar a característicageográfica específica desejada. Por exemplo, [Enter City-> Boston], "Boston" é casado comos nomes na Tabela Nomes de Localidade, retornando o NAMEJD para "Boston". [EnterStreet -> Adams]. A Tabela de Prioridade de Localidade de Característica é busca para umalista de FFJDs cujo NAMEJD é o NAMEJD para "Boston." A Tabela Encontrarcaracterística é buscada para o FEATJD que aponta para "Adams" no banco de dadosgeográficos. Subseqüentemente, o número de casa desejado pode ser solicitado a partir dousuário e a Tabela Encontrar Característica é buscada para o FEATJD que aponta para afaixa de endereços contendo o número de casa solicitado no banco de dados geográficos. ATabela Encontrar característica pode ser buscada para o FEATJD que aponta para o pontode latitude e longitude para essa característica no banco de dados geográfico, para exibirpara o usuário a localização da característica em um dispositivo ou aplicação de navegação,por exemplo. Para desempenho aperfeiçoado, o índice de localidade será freqüentementepré-compilado para eliminar muitas dessas referências indiretas.

Em modalidades, para uso de índice de localidade, em uma implementação bottom-up de encontrar endereços, uma lista de características geográficas alvo é escolhidaprimeiramente, então a característica correta é selecionada por resolver a localidadedesejada a partir da lista de todas as localidades contendo uma característica por aquelenome. Uma aplicação de navegação executará primeiramente o casamento para encontrar uma lista de características geográficas na tabela Encontrar Característica. Os FFJDscorrespondentes a partir da tabela Encontrar característica são então utilizados comoíndices para a tabela de Prioridade de Localidade de Característica. As entradas na tabelade prioridade para esses FFJDs podem ser então varridas para um NAMEJD cujo nome natabela de Nome de Localidade casa com a localidade desejada. Se o desenvolvedor de aplicações desejar apresentar opções de localidade para o usuário, a aplicação deveconsiderar os NAMEJDs de localidade em ordem de prioridade, escolhendo os nomes delocalidade com prioridade mais elevada que são exclusivos para os FFJDs emconsideração. Esses nomes podem ser então apresentados ao usuário a partir dos quaisescolher. Como no caso top-down, o índice de localidade será freqüentemente pré- compilado para eliminar muitas das referências indiretas entre as tabelas.

Em modalidades, o índice de localidade pode ser utilizado para encontrar lugaresnomeados como pontos de interesse e marcos. Listas de tais lugares são primeiramenteassociadas a segmentos de rua a partir do banco de dados geográficos de propriedade. Aaplicação casará então o nome do ponto de interesse ou marco desejado para encontrar o segmento de rua. A aplicação utiliza então a implementação de encontrar endereços acimautilizando o segmento de rua em ordem para determinar a localidade correta.

Em modalidades, o índice de localidade pode ser utilizado para encontrar um centrode cidade. Uma aplicação casará em nome a localidade desejada utilizando FULLJMAME eNAME_KEY na tabela de Nome de Localidade para encontrar a entrada correta na tabela. Após a entrada correta ser encontrada, o campo CENTERJD é utilizado para encontrar ainformação de centro de localidade de propriedade correspondente no banco de dadosgeográfico, como coordenadas de latitude e longitude ou segmento de rua correspondendoao centro de cidade.

Em modalidades, o índice de localidade pode ser utilizado para tornar desambígua localidade com nomes duplicatas, porém geografia distinta. Uma aplicação casará em nomea localidade desejada utilizando FULLJMAME e NAME_KEY na tabela de Nome deLocalidade para encontrar a entrada correta na tabela. Por exemplo, se a localidade for"Brentwood, Califórnia", dois casamento serão encontrados como mostrado na Figura 4. OADORNMENT a partir da tabela de Nome de Localidade será desse modo utilizado paracada localidade Brentwood, por exemplo adornos "Los Angeles" e "San Francisco." Essespoderiam ser exibidos para um usuário como "Brentwood (Los Angeles)" e "Brentwood (SanFrancisco)" a partir dos quais o usuário pode escolher.

Em modalidades, o índice de localidade pode ser utilizado para resolverambigüidade em características de endereço. Por exemplo, para o exemplo de "2 AdamsStreet" na Figura 3, a aplicação utilizará os nomes de localidades múltiplas ordenadas porPRIORIDADE para cada característica, para distinguir entre os quatro endereços "2 AdamsStreet" encontrados na localidade de Boston, Massachusetts. A aplicação primeiramenteencontrará segmentos de endereço que correspondem a endereços duplicatas no banco dedados geográficos, utilizando o campo FEATJD da tabela Encontrar Característica. Aaplicação encontrará então os FFJDs correspondentes na tabela Encontrar Características.

Os FFJDs são então utilizados como índices para a tabela de Prioridade de Localidade deCaracterística, localidades são recuperadas em ordem a partir da prioridade mais elevadapara a mais baixa utilizando PRIORIDADE até que um NAMEJD exclusivo seja encontradopara cada entrada FFJD. Os NAMEJDs são utilizados como índices para a tabela Nome deLocalidade para recuperar um nome de localidade exclusivo, FULLJMAME, para cadaendereço duplicata. No exemplo para "2 Adams Street", nomes de localidade exclusivosserão encontrados em Charlestown, Hyde Park1 Roxbury e Dorchester, todas sub-Iocalidades de Boston, Massachusetts.

Em modalidades, o índice de localidade pode ser utilizado para buscar áreasvizinhas para uma característica solicitada em uma aplicação top-down. Em alguns casosuma característica desejada pode não ser encontrada em uma localidade especificada porum usuário e a aplicação de navegação desejará expandir a busca para localidades decontenção maiores ou vizinhas. A aplicação primeiramente casará o nome da localidadedesejada na tabela de Nome de Localidade, recuperando o NAMEJD correspondente. Apósdeterminar que não há FFJDs correspondendo à característica solicita na tabela dePrioridade de Localidade de Característica com esse NAMEJD de localidade, a aplicaçãoencontrará um ou mais FFJDs na tabela de Prioridade de localidade de característica quecontém esse NAMEJD. A cadeia de prioridade pode ser seguida, prioridade mais elevadaou mais baixa, para esses FFJDs na tabela de Prioridade de Localidade de característicapara recuperar outros NAMEJDs que correspondem a esses FFJDs. A tabela EncontrarCaracterística pode ser consulta para determinar se o endereço solicitado está dentro dequalquer uma dessas outras localidades relacionadas.

Em modalidades, o exemplo de caso de uso a seguir ilustra a vantagem dacaracterística de priorização do índice de localidade. Sem priorização, não está claro para odesenvolvedor de aplicações como usar o nome mais reconhecível ao consultar o usuário.Em alguns lugares, nomes postais são os mais comuns. Em outras áreas, nomesadministrativos são bem conhecidos. Com a característica de priorização, o nome maiscomum pode ser escolhido.

Sem priorização:

Entrar rua -> Broadway

Por favor escolher entre ->

Broadway (Charlestown, MA)

Broadway (Manhattan, NY)

Com priorização:

Entrar rua -> Broadway

Por favor escolher entre ->

Broadway (Boston, MA)

Broadway (New York, NY)

Em modalidades, em um exemplo de caso de uso adicional como ilustrado naFigura 14, uma aplicação de navegação pode acomodar inconsistência quando uma cidadepróxima é erroneamente especificada. Cidades grandes como Chicago são genericamentecircundadas por subúrbios. Os subúrbios são separados, e têm sua própria estruturaadministrativa. Em particular, seus nomes de localidade diferem freqüentemente. Umusuário poderia não estar ciente da área suburbana, porém pensando somente na cidadecentral grande. Um exemplo é encontrado nos subúrbios ao norte de Chicago, comomostrado na Figura 14. Suponha que o usuário deseje localizar "Bryn Mawr Country Club"em Lincolnwood, porém somente conhece a área como Chicago. Se o usuário souber que oendereço da rua é "6600 North Crawford Ave." a entrada poderia prosseguir como a seguir:

Entrar estado -> Illinois

Entrar cidade -> Chicago

Entrar rua -> North Crawford Avenue

A aplicação de navegação observaria uma inconsistência aqui. A aplicaçãoprimeiramente buscará todos FFJDs na tabela de Prioridade de Localidade deCaracterística onde o NAMEJD aponta para Chicago. A aplicação observará que "NorthCrawford Avenue" não existe em Chicago. A aplicação buscará todos os FFJDs na tabelade prioridade de Localidade de Característica onde os FFJDs aponta para "North CrawfordAvenue." A aplicação encontrará "North Crawford Avenue" no subúrbio de Lincolnwood,Chicago. Se a aplicação tivesse encontrado "North Crawford Avenue" em várias localidades,a aplicação utilizaria o nome de localidade de prioridade mais elevado para esse FFJDutilizando PRIORIDADE na tabela de Prioridade de Localidade de característica. A aplicaçãopode observar que "South Crawford Avenue" existe em Chicago. A aplicação então solicita onúmero de rua:

Entrar número de rua -> 6600

Encontrado: "6600 North Crawford Avenue, Lincolnwood, Illinois"Nesse exemplo, se o número de rua correto foi encontrado nos dois lugares, aaplicação poderia oferecer para o usuário uma escolha: "6600 South Crawford Avenue,Chicago" ou "6600 North Crawford Avenue, Lincolnwood." Uma vez que o número da rua"6600" não é encontrado em "South Crawford Avenue" em Chicago, essa opção deendereço não é exibida para o usuário. Embora o número da rua "6600" encontrado para"North Crawford Avenue" seja localizado em Lincolnwood e não em Chicago, a aplicaçãopode assumir que é o endereço que o usuário pretende solicitar.

Em modalidades, em um exemplo de caso de uso adicional, a aplicação podefornecer manipulação de se uma de entradas de um usuário para a rua ou para a cidade éincompatível e deve ser fixa. O endereço para Chandler Music Hall em seu website é "71-73Main Street, Randolph, Vermont." Na cidade de Randolph, Main Street é dividido em "North Main Street" e um "South Main Street." "Main Street" também existe na cidade próxima deRandolf Center. Para o usuário final, se a rua for realmente Main Street, então o Hall deveestar em Randolf Center. Se o Hall estiver em Randolph, então é localizado em North MainStreet ou em South Main Street. O Hall é na realidade localizado em Randolph, em 71 NorthMain Street. Se um usuário final estivesse utilizando o endereço de website em umaaplicação top-down, o usuário seria corretamente levado a partir de Randolph para North ouSouth Main Street, porém a aplicação pediria a ele para uma decisão porque o número derua 71 existe nas duas ruas. Se o usuário estivesse utilizando o endereço de website emuma aplicação de bottom-up, o usuário seria levado incorretamente de Main Street paraRandolph Center. Em modalidades, um modo para uma aplicação de navegação tratardesse tipo de situação é apresentar todas as opções para o usuário:

Entrar estado -> Vermont

Entrar cidade -> Randolph

Entrar rua -> Main Street

Entrar número de rua ->71

Por favor escolher entre ->

71 North Main Street, Randolph

71 South Main Street, Randolph

71 Main Street, Randolph Center

Em modalidades, uma ou mais etapas da presente invenção são realizadasautomaticamente. A característica automática é implementada utilizando softwareapropriado. A característica automática cria um aumento substancial em eficiência evelocidade com as quais os índices de localidade são criados.As modalidades da presente invenção com modificação podem ser aplicadas emdispositivos e aplicações não de navegação. Por exemplo, em uma aplicação espacial dePáginas Amarelas, é desejável encontrar todas as firmas de um certo tipo separadas pordistância a partir de um ponto. Em modalidades, a indexação de localidades para esse tipode aplicação pode utilizar um esquema de prioridade com base em freqüência de ocorrênciaem um catálogo de Páginas amarelas.

A Figura 15 mostra um diagrama de blocos de um sistema exemplar 900 que podeser utilizado com modalidades da presente invenção. Embora esse diagrama representecomponentes como logicamente separados, tal representação é meramente para fins ilustrativos. Será evidente para aqueles versados na técnica que os componentes retratadosnessa Figura podem ser combinados ou divididos em componentes separados de software,firmware e/ou hardware. Além disso, será também evidente para aqueles versados natécnica que tais componentes, independente de como são combinados ou divididos, podemexecutar no mesmo sistema/dispositivo de computação ou podem ser distribuídos entre sistemas/dispositivos de computação diferentes conectados por uma ou mais redes ououtros meios de comunicação apropriados.

Como mostrado na Figura 15, o sistema 900 inclui tipicamente um dispositivo decomputação 910 que pode compreender uma ou mais memória 912, um ou maisprocessadores 914, e um ou mais dispositivos de armazenagem ou repositórios 916 de algum tipo. O sistema 900 pode incluir ainda um dispositivo de exibição 918, incluindo umainterface de usuário gráfico ou GUI 920 operando no mesmo pelo qual o sistema pode exibirmapas, e outras informações para um usuário. O usuário utiliza o dispositivo de computaçãopara solicitar, por exemplo, que uma localidade seja exibida em um mapa ou queorientações de direção sejam exibidas como uma rota em um mapa e/ou como direções de texto. A GUI 920 exibe um exemplo de um par de localidades duplicatas para "Washington,Nova Jérsei" e seus adornos "Easton" e "Hammonton." O usuário selecionará uma daslocalidades duplicatas a serem exibidas para GUI 920.

Um banco de dados geográficos 930 é mostrado como armazenagem externa parao dispositivo ou sistema de computação 910, porém o banco de dados geográficos 930 emalgumas ocorrências pode ser a mesma armazenagem que a armazenagem 916. Emmodalidades, entradas de nome de localidade são fundidas para localidades variantes eduplicatas 932 em banco de dados geográficos 930. Em modalidades, o banco de dadosgeográficos 930 contém uma máscara de fonte principal de fontes de localidade 934. Emmodalidades, um índice de localidade incluindo tabelas de Prioridade de Localidade decaracterística, Nome de localidade e Encontrar característica 936 é armazenado no bancode dados geográficos 930.

Software de criação de banco de dados geográficos de propriedade 930 podeutilizar fontes e definições de localidade de mundo real 960 para fundir e/ou adornar asentradas de nome de localidade variantes e duplicatas 932, criar a máscara de fonteprincipal de fontes de localidade 934 e criar o índice de localidade 936. Os exemplos defontes de localidade de mundo real e definições são descritos acima na discussão para a Figura 2. Informações a partir do banco de dados geográficos 930 são utilizadas por umsoftware de aplicação de dispositivo e conversor de banco de dados geográficos emaplicação 950, que é finalmente utilizado por um usuário do dispositivo de computação 910.O software de aplicação de dispositivo e conversor de banco de dados geográficos emaplicação 950 é mostrado remoto ao dispositivo de computação de usuário 910 porém também pode residir no dispositivo de computação de usuário 910.

Para um exemplo de um software de aplicação de dispositivo e conversor de bancode dados geográficos em aplicação 950, como utilizado por um usuário na Internet, ou emum dispositivo de navegação, o usuário pode selecionar uma localidade a ser exibida em ummapa. Alternativamente, se o usuário solicitar orientações de direção, por exemplo, alocalidade pode ser a localidade de partida ou término.

Em modalidades, o tipo de aplicação de software que consulta o usuário pode seruma aplicação drill-down, top-down ou bottom-up. A abordagem drill down é útil em sistemasde navegação baseados em carro com memória limitada. Em modalidades úteis paradispositivos de memória limitada, o desenvolvedor de aplicações pode incluir no dispositivo somente nomes de localidade que têm classificação elevada em prioridade. Uma aplicaçãotop-down solicita primeiramente ao usuário para entrar uma característica geográficaprincipal, por exemplo, um estado ou província. A aplicação então solicita que o usuárioentre uma localidade, por exemplo uma cidade ou cidade pequena, localizada nacaracterística geográfica principal. A aplicação solicita então que o usuário entre o nome da rua na localidade. Finalmente, a aplicação solicita que o usuário entre o número de rua. Namaioria dos casos, as consultas resultam em especificação de uma característica de bancode dados geográficos não ambígua para uso por uma aplicação, por exemplo, exibir alocalidade para o usuário em GUI 920 do dispositivo de exibição 918. Uma aplicaçãobottom-up solicita primeiramente que o usuário entre um número de casa e nome de rua. A aplicação então exibe todas as localidades nas quais um endereço pode ser encontrado.Finalmente, a aplicação solicita que o usuário escolha ou entre o nome da localidadedesejada. A metodologia bottom-up também resulta normalmente em especificação de umacaracterística de banco de dados geográficos não ambígua que pode ser então utilizadapela aplicação.

Em modalidades, o software de aplicação pode utilizar o índice de banco de dadosgeográficos em uma aplicação drill-down, que permite ao usuário final entrar um nome delocalidade parcial ou total, normalmente em um estado dado. Em modalidades, a aplicaçãoapresenta nomes para o usuário final que casam com a entrada do usuário, e o usuárioescolhe a melhor opção. Com o casamento contra os corpos de nome tokenizados, aaplicação pode apresentar tanto "Hollywood" como "West Hollywood" quando quaisquer dasprimeiras letras de "Hollywood" são entradas pelo usuário final.

Em outras modalidades, a aplicação de software não é uma aplicação drill-down eem vez disso consulta o usuário em relação ao número de rua e rua, localidade ecaracterística geográfica principal em um momento. Na maioria dos casos, a consultaresulta em especificação de uma característica de banco de dados geográficos nãoambígua, e o processo retorna a localização para o usuário. Se o usuário entrar um nomede rua de "Main street" e uma localidade de "Springfield", uma localidade duplicata"Springfield" será encontrada se também tiver uma rua pelo nome de "Main Street." Selocalidades duplicatas existirem para a característica geográfica, então uma lista delocalidades e seus adornos pode ser exibida para o usuário para pedir ao usuário paraescolher um, como em GUI 920 do dispositivo de exibição 918. Para um exemplo de par delocalidades duplicatas para "Washington, Nova jérsei", as duas localidades podem seradornadas com os condados nos quais são encontradas ou com nomes de cidades maiorespróximas. "Easton, Nova Jérsei" e "Hammonton, Nova Jérsei" respectivamente são cidadesgrandes próximas das duas localidades duplicatas. Desse modo, "Washington (Easton), NJ"e "Washington (Hammonton), NJ" são exibidas para a GUI 920 da Figura 15. Nesseexemplo, os adornos são apresentados em parênteses porém podem ser apresentados deoutras maneiras, como pelo uso de vírgulas para separar cada localidade duplicata a partirde seu adorno respectivo. O usuário seleciona uma das localidades duplicatas, e alocalidade em um mapa ou orientações de direção são então exibidas para o usuário.

A codificação de software apropriado pode ser facilmente preparada porprogramadores especializados com base nos ensinamentos da presente revelação, comoserá evidente para aquele versados na técnica de software. As modalidades da presenteinvenção podem ser implementadas também pela preparação de circuitos integrados deaplicação específica ou por interconexão de uma rede apropriada de circuitos decomponentes convencionais, como será prontamente evidente para aqueles versados natécnica.

As modalidades da presente invenção podem incluir um produto de programa decomputador que é um meio de armazenagem (meios) tendo instruções armazenadas nomesmo que pode ser utilizado para programar um computador para executar quaisquer dosprocessos de modalidades da presente invenção. O meio de armazenagem pode incluir,porém não é limitado a, qualquer tipo de disco incluindo discos flexíveis, discos ópticos,DVD, CD-ROMs, microdrive, e discos magneto-ópticos, ROMs, RAMs, EPROMs,EEPROMs, DRAMs, VRAMs, dispositivos de memória flash, cartões ópticos ou magnéticos,nanossistemas, incluindo Ics de memória molecular, ou qualquer tipo de sistema oudispositivo apropriado para armazenara instruções e/ou dados.

Armazenados em qualquer um dos meios legíveis por computador (meios), asmodalidades da presente invenção podem incluir software para controlar tanto o hardwaredo computador especializado/propósito geral ou microprocessador, e para permitir que ocomputador ou microprocessador interaja com um usuário humano ou outro mecanismoutilizando os resultados de modalidades da presente invenção. Tal software pode incluir,porém não é limitado a, acionadores de dispositivos, sistemas operacionais, e aplicações deusuário. Finalmente, tais meios legíveis por computador incluem ainda software paraexecutar modalidades da presente invenção, como descrito acima.

Incluído na programação ou software do microprocessador ou computadorespecializado/propósito final estão módulos de software para implementar os ensinamentosda presente invenção. As modalidades da presente invenção podem ser convenientementeimplementadas utilizando um microprocessador ou computador digital especializado ou depropósito geral convencional de acordo com os ensinamentos da presente revelação, comoserá evidente para aqueles versados na técnica de computador.

A descrição acima da presente invenção foi fornecida para fins de ilustração edescrição. Não se pretende que seja exaustiva ou limite as modalidades da presenteinvenção a formas precisas reveladas. Muitas modificações e variações serão evidentespara um técnico especializado na arte. As modalidades foram escolhidas e descritas paraexplicar melhor os princípios da presente invenção e sua aplicação prática, desse modopermitindo que outros versados na técnica entendam a presente invenção para váriasmodalidades e com várias modificações que são apropriadas para o uso específicoconsiderado. Pretende-se que o escopo da presente invenção seja definido pelasreivindicações a seguir e seus equivalentes.

Claims (45)

1. índice de localidade de banco de dados geográfico, armazenável em um meio dearmazenagem, CARACTERIZADO por compreender:um ponteiro para pelo menos um aspecto geográfico em um banco de dados geo-gráfico; eum conjunto de um ou mais nomes de localidade associado à pelo menos um as-pecto geográfico, onde um ou mais nomes de localidade são selecionados a partir de umaou mais fontes de nomes de localidade e são ordenados por prioridade com base em preva-lência de um ou mais nomes de localidade em uso comum para uma aplicação pretendida.

2. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que osaspectos geográficos compreendem ruas, segmentos de rua, margens de segmento de rua,partes dianteiras de bloco, marcos, parques estaduais, rodovias, centros de remessa, linhasferroviárias, rotas de ônibus, centros de remessa, locais comerciais e locais residenciais.

3. índice, de acordo com a reivindicação 1, CARACTERIZADO por compreenderainda uma máscara de fonte principal criada por alocar um bit para cada uma ou mais fon-tes de nome de localidade utilizadas no índice.

4. índice, de acordo com a reivindicação 3, CARACTERIZADO por compreenderainda uma máscara de fonte de localidade para cada localidade associada a cada aspectogeográfico, onde cada bit na máscara de fonte de localidade é definido se a localidade podeser encontrada na fonte para a qual um bit correspondente foi alocado na máscara de fonteprincipal.

5. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que aordem de prioridade pode ser aplicada diferentemente para atender usos comuns diferentes.

6. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que ouso comum para uma aplicação pretendida compreende o número mínimo de fontes no qualum nome de localidade pode ser encontrado se a aplicação for destinada a um usuário local.

7. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que ouso comum para uma aplicação pretendida compreende o número máximo de fontes noqual um nome de localidade pode ser encontrado se a aplicação for destinada para um usu-ário não local.

8. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que aprioridade de nomes de localidade para um aspecto geográfico com base em prevalência decada nome de localidade em uso comum para uma aplicação pretendida compreende umadeterminação da localidade com prioridade mais elevada associada a um aspecto geográfi-co para ser a localidade encontrada em uma fonte de nome postal preferida, então uma de-terminação de prioridade das localidades restantes associadas ao aspecto geográfico paraser pelo número de bits definidos em cada máscara de fonte de localidade, onde para as- localidades restantes, quanto maior o número de fontes de nome na máscara de fonte paraa localidade, mais elevada a prioridade da localidade.

9. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que aprioridade de nomes de localidade para um aspecto geográfico com base em prevalência de cada nome de localidade em uso comum para uma aplicação pretendida compreende umadeterminação de um número de fontes de nome de localidade na qual a localidade pode serencontrada a partir da máscara de fonte associada à localidade, em que quanto maior onúmero de fontes de nome na máscara de fonte para a localidade, mais elevada a priorida-de da localidade.

10. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de queuma prioridade alternada de nomes de localidades para um aspecto geográfico compreendeser baseado em uma determinação de um entre:um número de aspectos geográficos em cada localidade, em que quanto maior onúmero de fontes geográficas na localidade, mais elevada a prioridade da localidade;um tamanho físico de cada localidade, em que quanto maior o tamanho físico da lo-calidade, mais elevada a prioridade da localidade; eum tamanho de população de cada localidade, em que quanto maior o tamanho dapopulação da localidade, mais elevada a prioridade da localidade.

11. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de queuma prioridade alternada de nomes de localidades para um aspecto geográfico compreendeser baseado em uma determinação de uma preferência de uma certa fonte de nome de lo-calidade em relação a outras utilizando as máscaras de fonte de localidade, em que as loca-lidades tendo um conjunto de bits em suas máscaras de fonte de localidade para certa loca-lidade têm uma prioridade mais elevada do que localidades que não têm.

12. índice, de acordo com a reivindicação 3, CARACTERIZADO pelo fato de que amáscara de fonte principal compreende uma fonte de confiança, onde uma prioridade alter-nativa de nomes de localidade para um aspecto geográfico compreende ser baseado nafonte de confiança, em que localidades tendo um conjunto de bits em suas máscaras defonte de localidade para a fonte de confiança têm uma prioridade mais elevada do que Ioca- Iidades que não têm.

13. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que seuma determinação de prioridade de nomes de localidade para um aspecto geográfico resul-tar em um empate entre localidades, prioridade das localidades de empate compreende serbaseado em uma determinação de um entre:um número de aspectos geográficos em cada localidade de empate, onde quantomaior o número de fontes geográficas na localidade de empate, mais elevada a prioridadeda localidade de empate;um tamanho físico de cada localidade de empate, onde quanto maior o tamanho fí-sico da localidade de empate, mais elevada a prioridade da localidade de empate;um tamanho de população de cada localidade de empate, onde quanto maior o ta-manho da população da localidade de empate, mais elevada a prioridade da localidade deempate; euma preferência de uma certa fonte de nome de localidade em relação a outras uti-lizando as máscaras de fonte de localidade, em que localidades de empate tendo um con-junto de bits em suas máscaras de fonte de localidade para certa localidade têm uma priori-dade mais elevada do que localidades de empate que não têm.

14. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que aassociação de um nome de localidade a partir de um ou mais nomes de localidade com pelomenos um aspecto geográfico compreende associação direta ou indireta.

15. índice, de acordo com a reivindicação 14, CARACTERIZADO pelo fato de quea associação direta compreende uma fonte de nome de localidade específica associada aaspectos geográficos em geral, casando quaisquer aspectos geográficos associados aonome de localidade com pelo menos um aspecto geográfico no banco de dados geográficoutilizando pelo menos um atributo comum entre a fonte de nome de localidade e os aspectosgeográficos no banco de dados geográfico.

16. índice, de acordo com a reivindicação 15, CARACTERIZADO por compreenderainda um voto de facee tirado de aspectos geográficos casados em um mapa adjacente aum aspecto geográfico não casado no banco de dados geográfico para atribuir uma locali-dade ao aspecto geográfico não casado.

17. índice, de acordo com a reivindicação 16, CARACTERIZADO pelo fato de queum voto de facee compreende um entre um voto de maioria, um voto ponderado e um votode comprimento linear.

18. índice, de acordo com a reivindicação 14, CARACTERIZADO pelo fato de quea associação indireta compreende para uma primeira fonte de nome de localidade que não éassociada a aspectos geográficos em geral, nome de localidade de fonte cruzada casandocom uma segunda fonte de nome de localidade que é associada a aspectos geográficos éutilizado de tal modo que cada nome de localidade na primeira fonte herda as associaçõescom aspectos geográficos a partir da segunda fonte.

19. índice, de acordo com a reivindicação 1, CARACTERIZADO por compreenderainda um token principal do nome de localidade, em que o token principal é determinado porum ou mais entre tokenizar, normalizar e otimizar os nomes de localidade, bem como casaro nome de localidade com quaisquer nomes de localidade duplicatas ou similares.

20. índice, de acordo com a reivindicação 19, CARACTERIZADO pelo fato de quetokenizar compreende dividir os nomes de localidade em tokens, ou componentes.

21. índice, de acordo com a reivindicação 19,-CARACTERIZADO pelo fato de queo token principal compreende o corpo principal ou componente principal apropriado paraindexação.

22. índice, de acordo com a reivindicação 20, CARACTERIZADO pelo fato de quetokens além do token principal compreendem um ou mais entre um token de direção princi-pal, um token de tipo principal, um prenome ou informação de não tipo precedendo o corpo,um prefixo, um tipo traseiro, uma direção traseira, um sufixo, um identificador numérico queespecifica divisões da localidade, e um adorno ou nome de cidade facilmente reconhecível,próximo.

23. índice, de acordo com a reivindicação 19, CARACTERIZADO pelo fato de quenormalização compreende uma ou mais entre expandir abreviaturas, reduzir pontuação,remover espaços incorporados e normalizar em letras maiúsculas.

24. índice, de acordo com a reivindicação 19, CARACTERIZADO pelo fato de quea otimização compreende associar o nome de localidade com aspectos geográficos contidosna localidade.

25. índice, de acordo com a reivindicação 19, CARACTERIZADO pelo fato de quecasar o nome de localidade com quaisquer nomes de localidade duplicatas ou levementevariantes compreende concatenar tokens de nome de localidade e comparar tokens para onome de localidade com os tokens para quaisquer nomes de localidade similares ou duplica-tas para determinar casamentos.

26. índice, de acordo com a reivindicação 19, CARACTERIZADO pelo fato de queo casamento do nome de localidade com quaisquer nomes de localidade duplicatas ou le-vemente variantes compreende casar os nomes com base em sua representação fonéticaou por outro meio.

27. índice, de acordo com a reivindicação 26, CARACTERIZADO pelo fato de queo casamento compreende ainda comparar aspectos geográficos a partir da etapa de otimi-zação para o nome de localidade e quaisquer nomes de localidade duplicatas ou levementevariantes para determinar se essas localidades sobrepõem ou estão adjacentes.

28. índice, de acordo com a reivindicação 27, CARACTERIZADO pelo fato de quese todos os aspectos geográficos casam para o nome de localidade e quaisquer nomes delocalidades duplicatas ou levemente variantes esses nomes de localidade representam amesma localidade, e nomes de localidade duplicatas exceto um nome de localidade, sãoeliminados a partir do índice.

29. índice, de acordo com a reivindicação 27, CARACTERIZADO pelo fato de quese um ou mais porém não todos os aspectos geográficos casam para a localidade e quais-quer localidades duplicatas ou similares, esses nomes de localidade são considerados comorepresentando a mesma localidade e são fundidos em um nome de localidade no índice.

30. índice, de acordo com a reivindicação 29, CARACTERIZADO pelo fato de queuma união de todos os aspectos geográficos a partir de localidades que sobrepõem ou sãoadjacentes é associada ao nome de localidade fundido.

31. índice, de acordo com a reivindicação 27, CARACTERIZADO por compreenderainda adornos de cidades famosas, próximas, que são criados e armazenados no índicepara localidades separadas resultando se nenhum dos aspectos geográficos casar para alocalidade e quaisquer localidades duplicatas ou similares.

32. índice, de acordo com a reivindicação 1, CARACTERIZADO por compreenderainda um ou mais de números de identificação de aspecto geográfico, números de identifi-cação de localidade, pontos de latitude e longitude de centro de cidade de localidade, ador-nos de localidade, nomes completos de localidades e tamanho de localidades.

33. índice, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que oíndice é criado automaticamente.

34. Método para indexar uma localidade, CARACTERIZADO por compreender asetapas de:receber uma seleção de um ou mais aspectos geográficos a partir de um banco dedados geográfico;determinar um conjunto de um ou mais nomes de localidade a partir de um conjuntode uma ou mais fontes de nome de localidade;associar os nomes de localidade aos aspectos geográficos do banco de dados ge-ográfico;priorizar para cada aspecto geográfico os nomes de localidade associados em or-dem de prevalência em uso comum para uma aplicação pretendida; eordenar os nomes de localidade associados a cada aspecto geográfico por priori-dade.

35. Sistema que inclui funcionalidade para habilitar um usuário a acessar localida-des e aspectos geográficos nas localidades, CARACTERIZADO por compreender:um índice de banco de dados geográfico tendo pelo menos um aspecto geográficoem um banco de dados geográfico e um conjunto de um ou mais nomes de localidade asso-ciados a pelo menos um aspecto geográfico, em que um ou mais nomes de localidade sãoselecionados a partir de uma ou mais fontes de nome de localidade e são ordenados porprioridade com base em prevalência do nome de localidade em uso comum para uma apli-cação pretendida; eum programa de aplicação que utiliza o índice de banco de dados geográfico emcombinação com a exibição de informações de aspecto geográfico e localidade para umusuário e com recebimento de entrada a partir de um usuário.

36. Sistema, de acordo com a reivindicação 36, CARACTERIZADO pelo fato deque a exibição de informações de aspecto geográfico e localidades compreende um ou maisde exibição textual de informações de aspecto geográfico e localidade para um usuário, exi-bição da localização dos aspectos geográficos em um mapa para o usuário e exibição deinformações de roteamento em um mapa para o usuário.

37. Sistema, de acordo com a reivindicação 35, CARACTERIZADO pelo fato deque o sistema compreende um sistema baseado na Internet.

38. Sistema, de acordo com a reivindicação 35, CARACTERIZADO pelo fato deque o sistema compreende um sistema de navegação no veículo.

39. Dispositivo portátil que inclui funcionalidade para habilitar um usuário a acessarlocalidades e aspectos geográficos nas localidades, CARACTERIZADO por compreender:um índice de banco de dados geográfico tendo pelo menos um aspecto geográficoem um banco de dados geográfico e um conjunto de um ou mais nomes de localidade asso-ciado a pelo menos um aspecto geográfico, em que um ou mais nomes de localidade sãoselecionados a partir de uma ou mais fontes de nome de localidade e são ordenados porprioridade com base em prevalência do nome de localidade em uso comum para uma apli-cação pretendida; eum programa de aplicações que utiliza o índice de banco de dados geográfico emcombinação com a exibição de informações de aspectos geográficos e localidade para umusuário e com recebimento de entrada a partir de um usuário.

40. Dispositivo portátil, de acordo com a reivindicação 39, CARACTERIZADO pelofato de que a exibição de informações de aspecto geográfico e localidade compreende umou mais de exibição textual de informações de aspecto geográfico e localidade para um u-suário, exibição da localização dos aspectos geográficos em um mapa para o usuário e exi-bição de informações de roteamento em um mapa para o usuário.

41. Dispositivo portátil, de acordo com a reivindicação 39, CARACTERIZADO pelofato de que o dispositivo portátil compreende um assistente pessoal digital (PDA).

42. Dispositivo portátil, de acordo com a reivindicação 39, CARACTERIZADO pelofato de que o dispositivo portátil compreende um sistema de navegação pessoal.

43. Dispositivo portátil, de acordo com a reivindicação 39, CARACTERIZADO pelofato de que o dispositivo portátil compreende um telefone celular.

44. Programa de aplicações baseado em Sistemas de Informações geográficas(GIS) que inclui funcionalidade para habilitar um usuário a acessar localidades e aspectosgeográficos nas localidades, CARACTERIZADO por compreender:um índice de banco de dados geográfico tendo pelo menos um aspecto geográficoem um banco de dados geográfico e um conjunto de um ou mais nomes de localidade asso-ciado a pelo menos um aspecto geográfico, em que um ou mais nomes de localidade sãoselecionados a partir de uma ou mais fontes de nome de localidade e são ordenados porprioridade com base em prevalência do nome de localidade em uso comum para uma apli-cação pretendida.

45. Meio legível por máquina, incluindo operações armazenadas no mesmo que,quando processadas por um ou mais processadores, CARACTERIZADO pelo fato de fazercom que um sistema execute as etapas de:receber uma seleção de aspectos geográficos a partir de um banco de dados geo-gráfico;determinar um conjunto de um ou mais nomes de localidade a partir de um conjuntode uma ou mais fontes de nome de localidade;associar os nomes de localidade aos aspectos geográficos a partir do banco de da-dos geográfico;priorizar para cada aspecto geográfico os nomes de localidade associados em or-dem de prevalência em uso comum para uma aplicação pretendida; eordenar os nomes de localidade associados a cada aspecto geográfico por priori-dade.