Unindo duas tabelas em uma consulta complexa (dados não uniformes)

SELECT DISTINCT ON (1)
       t.id, d.address, d.id
FROM   data_table t
JOIN   dictionary d ON replace(d.address, ' ', '')
                 LIKE (replace(t.address, ' ', '') || '%')
ORDER  BY t.id, d.address, d.id

(ORDER BY atualizado após a atualização da pergunta.) Sem ORDER BY está escolhendo uma correspondência arbitrária.
Explicação da técnica nesta resposta relacionada:
Selecionar a primeira linha em cada grupo GROUP BY?

Um índice funcional em seu dicionário tornaria isso rápido :

CREATE INDEX dictionary_address_text_pattern_ops_idx
ON dictionary (replace(address, ' ', '') text_pattern_ops);

Mais explicações para isso na resposta que forneci para a pergunta anterior .

Pode-se debater se isso lhe dá a "melhor" combinação. Uma alternativa seria uma correspondência de similaridade com um índice de trigrama. Detalhes no primeiro dos links que adicionei à sua última pergunta.