Unir dos tablas en una consulta compleja (no datos 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 actualizado después de la actualización de la pregunta). Sin ORDER BY está eligiendo una coincidencia arbitraria.
Explicación de la técnica en esta respuesta relacionada:
¿Seleccionar la primera fila en cada grupo GROUP BY?

Un índice funcional en su diccionario haría esto rápido :

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

Más explicación para eso en la respuesta que proporcioné a la pregunta anterior .

Uno podría debatir si eso te da la "mejor" coincidencia. Una alternativa sería una coincidencia de similitud con un índice de trigrama. Detalles en el primero de los enlaces que agregué a tu última pregunta.