Classificando uma lista de cadeias em ordem lexicográfica de cadeias ordenadas

Seja uma coleção de seqüências de caracteres sobre o alfabeto que no total contêm símbolos.$A$$\{0,\ldots,m-1\}$$n$

Sua tarefa é classificar cada uma das cadeias internamente e, em seguida, classificar as cadeias resultantes em ordem lexicográfica. (Seu algoritmo não precisa operar dessa maneira.)

Exemplo:

Entrada: 33123 15 1 0 54215 21 12

Saída: 0 1 12 12 12333 12455 15

Eu encontrei uma maneira de fazê-lo no tempo e no espaço .$O(m+n)$$O(mn)$

O espaço é maior que o tempo, porque eu uso uma matriz inteligente que permite criar uma matriz com tamanho e fornecer valores iniciais para todas as células em .$n$$O(1)$

Usei a classificação de bucket para classificar cada sequência de caracteres ( tempo e espaço) e árvores de palavras para classificar a coleção si ( tempo e espaço). mas minha solução é muito complicada.$O(m+n)$$A$$O(m+n)$$O(mn)$

Alguém tem uma solução melhor, com tempo e menos espaço, ou mais rápido que ?$O(m+n)$$O(m+n)$

A solução deve ser determinística para que não haja mapas de hash ou outros algoritmos estatísticos

Minha solução: Uma matriz inteligente é uma matriz de tamanho que podemos criar e "inicializar" em :$m$$O(1)$

Criamos três matrizes do tamanho de sem inicializar qualquer um deles e nós também manter uma variável inteira single chamado .$m$$C$

A primeira matriz contém os dados. A segunda matriz contém ponteiros para uma célula na terceira matriz. A terceira matriz contém ponteiros para uma célula na segunda matriz. contém o número de células inicializadas até o momento.$C$

Suponha que gostaríamos de definir o valor da célula (suponha que seja a primeira vez que o fazemos nesta célula). Em seguida, iremos para a célula na primeira matriz e a definiremos para o valor desejado.$i$$i$

Agora vamos para a célula na segunda matriz e configuramos para apontar para a célula na terceira matriz. Defina a célula na terceira matriz para apontar para a célula na segunda matriz. Aumente em 1.$i$$C$$C$$i$$C$

Suponha que gostaríamos de saber se a célula é uma lixeira (isso significa que ainda precisamos definir algo para ela).$j$

Iríamos para a célula na segunda matriz e olharíamos para o número da célula (na terceira matriz) que a célula (na segunda matriz) aponta para - nós a chamaremos de .$j$$j$$k$

Se então é lixo (porque só inicializamos células até agora não é uma delas).$k>C$$j$$C$$j$

Se , veremos para que célula (na terceira matriz) aponta. Se não for então é lixo. Caso contrário, não é lixo$k<C$$k$$j$$j$$j$

Dessa forma, podemos saber em cada etapa se inicializamos esta célula e se não inicializamos. Então, criamos e "inicializamos" uma matriz de tamanho em tempo.$m$$O(1)$

O principal truque não é inicializar toda a matriz no início, mas encontrar uma maneira de saber quais células inicializamos até agora e inicializar uma célula apenas quando "olhamos" para ela. No modelo de RAM, leva tempo para criar uma matriz de qualquer tamanho sem inicializá-la.$O(1)$

Uma árvore de palavras da ordem m é uma generalização de um TRIE. Cada nó contém uma matriz de ponteiros para seus filhos. O tamanho da matriz é . Cada nó também contém um contador para dizer quantos conjuntos existem descritos por este nó.$m$

Como usamos matrizes inteligentes cada vez que adicionamos uma palavra (um conjunto), são necessários apenas tempo e espaço .$A$$O(|A|)$$O(m|A|)$

Você também pode resolver isso no tempo e no espaço :$O(n \log n)$$O(n)$

• Primeiro, classifique cada palavra usando o mergesort. O tempo de execução disso será no máximo e o uso do espaço é .$O(n \log n)$$O(n)$

• Em seguida, armazene todas as palavras em uma palavra. O tempo e o espaço para isso serão , se você implementar a palavra tentar corretamente. Em particular, em cada nó da árvore, você deve armazenar o conjunto de filhos como uma hashtable (não como uma matriz). Dessa maneira, o armazenamento em um nó é proporcional ao número de filhos que ele possui e a pesquisa para encontrar um filho pode ser feita no tempo . Assim, o tempo de execução desse estágio é tempo e espaço.$O(n)$$O(1)$$O(n)$$O(n)$

• Por fim, leia todas as palavras do artigo. Isso envolve pegar cada hashtable e classificar seu conteúdo, por exemplo, usando o mergesort. Todas essas etapas de classificação levarão no máximo .$O(n \log n)$

A estrutura de dados resultante parece bastante simples. É especialmente simples se você implementar em uma linguagem que tenha suporte embutido para hashmaps (por exemplo, Javascript, Python).

Como alternativa, você pode substituir o hashmap por uma estrutura de dados da árvore binária balanceada e obter um tempo de execução semelhante.

Como uma observação geral sobre "matrizes inteligentes":

Você pode substituir o uso de "matrizes inteligentes" por uma hashtable. Dessa forma, você preservará a capacidade de realizar leituras e gravações de tempo (esperado). Em particular, em vez de definir , você armazena o valor na chave (por exemplo, adicione o mapeamento à hashtable). Quando você quiser ler o valor de , procure na hashtable e retorne o que encontrar lá. Dessa maneira, o uso do espaço é proporcional ao número de entradas inicializadas na "matriz inteligente" e cada acesso leva o tempo (esperado).$O(1)$$A[i] := v$$v$$k$$k \mapsto v$$A[i]$$i$$O(1)$

Você pode classificar um conjunto de cadeias de caracteres sobre um alfabeto inteiro de tamanho usando um trie em tempo e no espaço, onde é a distinção prefixo de .$S$$\{0,1,\dots,\sigma-1\}$$\sigma$$O(d\sigma)$$d$$S$

Aqui está uma solução que não usa tabelas de hash.

Deixe ser comprimento do prefixo curto da cadeia que a distingue das outras cordas em . O prefixo distintivo de é definido como .$d_s$$s \in S$$S$$S$$d = \sum_{s\in S}d_s$

O algoritmo para resolver o problema usa uma abordagem de dividir e conquistar, é um RadixSort que começa no dígito mais significativo (char).

1) Crie buckets$\sigma$$0,1,\dots,\sigma-1$

2) Processe as strings caractere por caractere desde o início e distribua-as em buckets usando CountingSort no tempo .$\sigma$$O(1)$

3) Repita o processo em buckets contendo mais de um elemento usando o próximo caractere para classificá-los.

4) Concatene os grupos da esquerda para a direita para obter a sequência ordenada.

Esse algoritmo gera uma série -ary, na qual cada nó é uma matriz do tamanho e as seqüências são armazenadas nas folhas.$\sigma$$\sigma$

Aqui está um exemplo.

Vamos ser e .$\sigma$$5$$S=\{410,013,042,111,001,444\}$

A seguir, é apresentado o trie gerado pelo algoritmo:

Cada string indica um caminho de tamanho antes que o nó que aponta para seja criado. Cada nó desses caminhos leva espaço e tempo para ser alocado.$s$$O(d_s)$$s$$O(\sigma)$$O(\sigma)$