Re-Pair es un esquema de compresión de gramática con tasas de compresión favorablemente buenas. La computación de Re-Pair viene con el costo de mantener grandes tablas de frecuencia, lo que hace difícil computar Re-Pair en conjuntos de datos a gran escala. Como solución a este problema, presentamos, dado un texto de longitud cuyos caracteres provienen de un alfabeto entero con tamaño , un algoritmo de tiempo que calcula Re-Pair con bits de espacio de trabajo incluyendo el espacio del texto, donde es una constante definida por el usuario y es la suma de y el número de no terminales. Damos variantes de nuestra solución que funcionan en paralelo o en el modelo de memoria externa. Desafortunadamente, el algoritmo parece no ser práctico ya que una versión preliminar ya necesita aproximadamente una hora para calcular Re-Pair en un megabyte de texto.