Función de derivación de plantillas de SMS basada en un algoritmo de programación dinámica

Uno de los microservicios de los que somos responsables proporciona la interfaz SMS completa para cada línea de negocio de la empresa.

Debido a las políticas cada vez más estrictas de los operadores de telecomunicaciones, cada vez es más difícil enviar mensajes de texto.

Cada proveedor de servicios de SMS ha presentado requisitos similares para informar las plantillas de SMS; de lo contrario, la tasa de envío de SMS se verá afectada.

De forma general, cada sistema realizará informes incrementales al proveedor del servicio SMS al enviar nuevos mensajes de texto.

Pero una vez que cambias de proveedor de servicios, necesitas organizar todas las plantillas de mensajes de texto.

La clasificación manual de plantillas de mensajes de texto anteriores requiere la participación de personal de varias líneas de negocios, lo que requiere mucha mano de obra y es propenso a fugas.

El mantenimiento de los documentos de plantilla de SMS se puede utilizar como una solución futura, pero el primer uso aún requiere la clasificación manual de las plantillas de SMS anteriores, lo que no puede evitar la carga de trabajo.

Por lo tanto, considere analizar automáticamente las plantillas de mensajes de texto recopilando mensajes de texto en los últimos 1 a 3 meses.

Después de la investigación, PHP proporciona similar_text() para calcular la similitud del texto. La complejidad temporal de un solo mensaje de texto es O(n^3)

Entonces podemos recorrer los mensajes de texto por. estableciendo un umbral razonable Ejemplos grabados y generados, ejemplos de SMS generados.

La complejidad temporal de todo el script es O (m.n) m: número de registros de SMS n: número de plantillas de SMS

El número promedio de plantillas es 200 y hemos cambiado 6 veces por diversos motivos.

Con la solución anterior, es necesario extraer manualmente contenido dinámico sin plantilla para cada informe centralizado, lo cual no es eficiente.

Por lo tanto, se necesita una herramienta de análisis de plantillas.

Debido a que el contenido dinámico de las plantillas de SMS suele estar en formatos comunes, como nombres, no se puede analizar utilizando métodos tradicionales como expresiones regulares, y no se han encontrado bibliotecas de clases, herramientas o métodos relevantes.

Considere comparar cadenas similares con alta similitud y extraer continuamente cadenas públicas para aproximarse a la plantilla de SMS.

Para dos cadenas de longitud n, la cadena pública más larga se cuenta de acuerdo con el método transversal de doble puntero convencional. Después de las pruebas en el entorno fuera de línea, ya no es posible cuando la longitud del mensaje de texto es superior a 30. caracteres El cálculo para calcular dos mensajes de texto se completa dentro del tiempo normal, es decir, el análisis de mensajes de texto no se puede utilizar para ningún mensaje de texto de marketing largo.

Porque, de hecho, la complejidad de tiempo requerida para calcular la cadena pública de dos mensajes de texto es O (2 ^ n). La longitud promedio de n mensajes de texto no se puede utilizar como un pequeño coeficiente constante cuando n es. mayor que 20. negligencia.

Es decir, la complejidad temporal de todo el script aumenta a O (m.n.2^l) m: Número de registros de SMS n: Número de plantillas de SMS l: Longitud promedio de SMS

Continúa a continuación para mayor comodidad Descripción, definición

SMS A es la cadena A: sus elementos son a1, a2...an..aN

SMS B es la cadena B: su elemento es b1 ,b2....bm..bM

La cadena pública correspondiente a a1~an y b1~bm se llama c(m,n)

O(2 ^n+ m) Se utiliza mucho tiempo para calcular las cadenas comunes de los respectivos subconjuntos de los subproblemas superpuestos a1, a2....an..aN, b1, b2....bm..bM, siempre y cuando Como los términos repetidos de orden inferior se pueden separar, la idea de dp se puede utilizar para reducir la complejidad del tiempo.

Tome cualquier subcadena a1~an del mensaje de texto A y la subcadena b1~bm de B

Es obvio:

Es decir, de hecho, an es conocido En el caso del valor de bm, solo es necesario conocer la información de los tres valores intermedios de c(n-1,m-1), c(n-1,m), c(n,m -1) Calcule c (n, m) directamente, es decir, c (n, m) se puede reducir como máximo n + m veces sin tener que atravesar completamente las dos cadenas, y se elimina el costo de cálculo repetido.

Para ello, guardamos una matriz de longitud N*M para guardar la longitud de todos los valores intermedios de c(n,m).

Además, para restaurar la dirección de crecimiento de la cadena atómica, es necesario registrar que cada c(n,m) está compuesto por c(n-1,m-1),c (n-1,m),c ¿Cuál de (n,m-1) se calcula?

Matriz

De la matriz anterior, podemos saber que los dos públicos * ** las cadenas son *Good Chen* Niu. El tiempo de este algoritmo está optimizado de O(2^(M+N)) a O(M*N) M: longitud de la cadena A, longitud de N cadena B

Macroscópicamente, el tiempo de todo el script La complejidad vuelve a O(m.n) m: número de registros SMS n: número de plantillas de SMS.

El script se puede ejecutar online en escala de grises o completo sin ningún problema y se consigue el objetivo.