O arquivo específico que você está procurando encontra-se em pacote libicu55 nos arquivos do Xenial. Não aparece nos arquivos do Trusty ou do Zesty, no entanto.
Se você estiver executando o Xenial, você poderá instalar isso com sudo apt install libicu55