Frequência de palavras com pedidos na complexidade O (n)

11

Durante uma entrevista para uma posição de desenvolvedor Java, me perguntaram o seguinte:

Escreva uma função que use dois parâmetros:

  1. uma String representando um documento de texto e
  2. um número inteiro fornecendo o número de itens a serem retornados.

Implemente a função para que ela retorne uma lista de Strings ordenadas por frequência de palavra, a palavra que ocorre com mais frequência primeiro. Sua solução deve ser executada em O(n) tempo em que n é o número de caracteres no documento.

A seguir é o que eu respondi (em pseudocódigo), não é mas sim O ( n log n ) tempo por causa da classificação. Não consigo descobrir como fazê-lo O ( n ) tempo. O(n)O(nlogn)O(n)

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Alguém sabe ou pode me dar algumas dicas?

user2712937
fonte
11
Use uma tabela de hash.
Yuval Filmus
O uso de uma hashtable não resolve o problema. Além disso, a hashtable é o Java herdado.
user2712937
As tabelas de hash geralmente são o truque para reduzir a complexidade de para O ( n ) . Mesmo que sejam Java legado, o que isso significa. Eu não verifiquei esse caso em particular, então você pode estar certo. O(nlogn)O(n)
Yuval Filmus
@YuvalFilmus. Obrigado, mas a tabela de hash é praticamente a mesma do mapa de hash, que eu já estou usando (a principal diferença entre a estrutura de 2 dados é a sincronização, que não se aplica aqui). O log (n) no meu vem da classificação dos valores no mapa de hash.
user2712937
3
A propósito, este site se concentra em conceitos e algoritmos, não em código. Portanto, normalmente solicitamos que você remova o código Java e forneça uma descrição conceitual de sua abordagem (possivelmente com pseudocódigo conciso de alto nível, se necessário). Além disso, neste site a questão relevante é quais estruturas e algoritmos de dados usar; a API Java específica Hashtablenão é relevante para este site (mas você pode perguntar sobre isso no StackOverflow) e, da mesma forma, se é Java legado ou não, é realmente irrelevante para os propósitos deste site.
DW

Respostas:

10

Sugiro uma variação da contagem de distribuição:

  1. Leia o texto e insira toda a palavra encontrada em uma tentativa , mantendo em cada nó uma contagem, com que frequência a palavra representada por esse nó ocorreu. Além disso, mantenha o controle da maior contagem de palavras, digamos maxWordCound. - O(n)
  2. Inicialize uma matriz de tamanho maxWordCount. Tipo de entrada são listas de strings. - , já que a contagem não pode ser maior.O(n)
  3. Atravesse o trie e, para cada nó, adicione a sequência correspondente à entrada da matriz indicada pela contagem. - , já que o comprimento total das cadeias é limitado por n .O(n)n
  4. Atravesse a matriz em ordem decrescente e produza o número desejado de strings. - , uma vez que isso é um limite para o tamanho e a quantidade de dados na matriz.O(n)

Provavelmente, você pode substituir o teste por outras estruturas de dados na primeira fase.

FrankW
fonte
+1, embora eu não tenha certeza disso. É O (n), pois o número de palavras a retornar é limitado por n, o número de caracteres, mas é isso que a pergunta faz? Ou um resultado independente do número de palavras retornadas?
Nikos M.
@NikosM. Ele é ; é um limite superior do pior caso geral para o número de palavras retornadas, não as suposições necessárias. n
Raphael
@Raphael, yeap corrigir estou pensando sobre isso desde que foi perguntado em uma entrevista, truques possíveis na questão ..
Nikos M.
Gostaria de saber se existe um algoritmo de tempo linear de espaço eficiente.
precisa saber é
3
@ saadtaame, sim, essa é uma pergunta interessante. Pode valer a pena postar separadamente como uma pergunta separada. Não é apenas eficiência de espaço; a solução trie também é intensiva em ponteiros, o que pode torná-la mais lenta na prática (considerando como a hierarquia de memória funciona em máquinas reais). "Eficiência" é diferente do pior caso de execução. Não é incomum que um algoritmo de tempo limpo supere um algoritmo de tempo O ( n ) intensivo em ponteiro , portanto essa pergunta já parece estar descartando alguns algoritmos em potencial que podem ser uma escolha melhor na prática. O(nlgn)O(n)
DW
3

A coleta de contagens de ocorrências é O (n), portanto, o truque é realmente encontrar apenas as contagens de k principais ocorrências.

Um heap é uma maneira comum de agregar os principais valores de k, embora outros métodos possam ser usados ​​(consulte https://en.wikipedia.org/wiki/Partial_sorting ).

Assumindo que k é o segundo parâmetro acima e que é uma constante na declaração do problema (parece ser):

  1. Crie uma série de palavras com a contagem de ocorrências em cada nó.
  2. Inicialize um monte de tamanho k.
  3. Atravesse a trie e min-probe / insira cada par (folha, número de ocorrências) no heap top-k.
  4. Faça a saída das k folhas e contagens superiores (isso é realmente meio complicado, porque você precisa de indicadores pai para mapear cada folha de volta a uma palavra).

Como o tamanho do heap é uma constante, as operações do heap são O (1), portanto, a etapa 3 é O (n).

O heap também pode ser mantido dinamicamente ao criar o trie.

KWillets
fonte
2

Seu algoritmo nem roda no tempo ; inserir Θ ( n ) coisas em um hashtable custa tempo Ω ( n 2 ) já (na pior das hipóteses).O(nlogn)Θ(n)Ω(n2)


O que se segue está errado ; Estou deixando aqui por enquanto para fins ilustrativos.

O algoritmo a seguir é executado no pior dos casos (assumindo um alfabeto Σ de tamanho constante), n o número de caracteres no texto.O(n)Σn

  1. Construa uma árvore de sufixos do texto, por exemplo, com o algoritmo de Ukkonen .

    Se a construção ainda não fizer isso, adicione o número de folhas alcançáveis ​​em cada nó (interno).

  2. Atravesse a árvore da raiz e corte todos os galhos no primeiro espaço (branco).

  3. Atravesse a árvore e classifique a lista de filhos de cada nó pela contagem de folhas.

  4. O rendimento da árvore (folhas da esquerda para a direita) agora é uma lista de todas as palavras, classificadas por frequência.

Em relação ao tempo de execução:

  1. O algoritmo de Ukkonen (em sua forma aprimorada) é executado no tempo ; manter a contagem de folhas não aumenta ΘO(n)Θ -Custo do algoritmo.
  2. Temos que percorrer um nó por caractere de cada palavra que ocorre no texto. Como existem no máximo pares diferentes de caracteres de palavras, visitamos no máximo n nós.nn
  3. Visitamos no máximo nós (cf. 2.) e gastamos tempo O ( | Σ |log | Σ | ) = O ( 1 ) por nó.nO(|Σ|log|Σ|)=O(1)
  4. Podemos obter o rendimento (que obviamente tem tamanho ) por uma simples travessia no tempo O ( n ) (cf. 2.).O(n)O(n)

Limites mais precisos podem ser obtidos parametrizando o tempo de execução com o número de palavras diferentes; se houver poucos, a árvore será pequena após 2.

Rafael
fonte
O algoritmo está incorreto (não classifica). Não tenho mais certeza de que o tempo linear seja possível.
Raphael
1

HashMap1..nO(n)O(n)

O(n)O(n)O(n)

Ou, se você quiser jogar um pouco mais seguro, antes de dar uma resposta, primeiro pergunte "você se importa com a diferença entre esperadoO(n) running time and worst-case O(n) running time?". Then tailor your answer accordingly. Be prepared for the interviewer to ask you how you would choose, in practice. (If so, score! That's a question you should be able to hit out of the ballpark.)

D.W.
fonte
Storing Θ(n) things in a hashtable takes Ω(n2) time in the worst-case already.
Raphael
I can't speak for the interviewers, but I'm hesitant to use their sloppiness as excuse for more of the same. Also, this site is about the science (as you yourself commented above), not about hand-waving "how will I get paid sooner" programming tricks.
Raphael
Desde que esse entendimento seja explicitado, eu estou bem com isso. Eu já vi muitas perguntas aqui que foram confundidas porque algum "entendimento" implícito promoveu idéias erradas.
Raphael
0

Hashtable based solution

Not sure why hashtable makes the complexity Ω(n2) if n is the number of characters (not words).

If you iterate through every character in the document and as you are iterating, calculate the hashcode of the word, you will have gone through n characters. That is, as soon as a letter is encountered, the word begins, so start computing hash until the word ends (there are some special cases for punctuation but those do not affect the complexity). For every word, once the hash is computed, add it to a hashtable. This is to avoid going over every word twice, i.e. first to iterate through the document to find the words and then to insert them in a hashtable, although the complexity in that case could also be Ω(n).

Collisions in the hashtable are surely a problem, and depending on how big the original hashtable was and how good the hashing algorithm is, one could approach close to O(1) for insertions and keeping counts and thus O(n) for the algorithm, although at the expense of memory. However, I still cannot appreciate how the worst case can be asserted to be O(n2) if n is the number of characters.

The assumption is that the hashing algorithm is linear in time in relation to the number of characters.

Radix sort based solution

Alternatively, assuming English, since the length of the words is well-known, I would instead create a grid and apply radix sort which is O(kN) where k would be the maximum length of a word in the English language, and N is the total number of words. Given n is the number of characters in the document, and k is a constant, asymptotically this amounts O(n).

Now count the frequency of each word. Since the words are sorted, we will be comparing each word to its preceding word to see if it's the same one or different. If it's the same, we remove the word and add a count to the previous. If different, just make the count 1 and move on. This requires 2n comparisons where n is the number of characters, and thus O(n) in complexity as a whole.

The top few longest words in English are ridiculously long, but then one could cap the word length at a reasonable number (such as 30 or smaller) and truncate words accepting the margin of error that might come with it.

Omer Iqbal
fonte
(1) Since in most texts the maximum length of the words is bounded by a constant, the number of words is Θ(n) as well. (2) Depending on the hash function, it may not be possible to compute the hash on the fly while reading the word. (3) In the worst case, all words hash to the same location in the table, making insert and lookup Θ(n).
FrankW
Hi FrankW. (2) I am stating that we could pick function (i.e. a rolling hash) that we can compute on the fly. Even if not, the overall complexity does not change as long as hashing is linear time, because reading and hashing would be O(n+n) operations. (3) Of course, but that depends on the choice of algorithm again. There are many algorithms that do substantially better if the words are different. For the same word, you just increase the count on a single entry. As an analogy, when I have to pick a sorting algorithm, worst case can be O(n2) but I typically pick better :-)
Omer Iqbal
(3) Whatever hash function you choose, I can come up with an input where that specific function degrades. And choosing the hash function after knowing the input is usually not an option. (And remember that the comment you were presumably addressing was about the worst case, not the typical case.)
FrankW
Why does a hash table lead to O(n2) worst-case complexity? It's because in principle the worst-case running time of a hashtable is very bad. In practice this worst-case almost never seems to eventuate (particularly if you choose the hash function correctly, with randomization and other techniques), and one can even prove theorems to justify why that is so, but if this is a question about asymptotic complexity, practical considerations like that arguably go out the window (or at least that's the argument you may hear).
DW
Ordinary hash tables inserts are O(n2) because a collision requires the item to be placed elsewhere. Here, we do not need to insert the duplicates. 1) Same word repeats: then up the count, this is guaranteed to be O(1)mais tempo de hash. 2) Palavras diferentes mesmo hash: é aí que está a questão de quão bom / ruim é o hash e se o tamanho da tabela é muito pequeno. Eu concordo que éΩ(1 1), mas, dependendo das escolhas, também afirmei que "é possível aproximar -seO(1 1) para inserções e manutenção de contagens ". Poderíamos discutir qual tamanho e função da tabela poderia nos aproximar O(1 1).
Omer Iqbal