Gale_and_Church_Algorithm.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Gale and Church Algorithm",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyO00dzebIc6KU8KikANiS4p",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/quocthang0507/VietnameseNaturalLanguageProcessing/blob/main/Gale_and_Church_Algorithm.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6Q1sp1h8xw0s"
      },
      "source": [
        "# A statistical length-based sentence alignment using [Gale and Church](http://acl.ldc.upenn.edu/J/J93/J93-1004.pdf) algorithm\n",
        "\n",
        "Referenced from https://github.com/alvations/gachalign/blob/master/gale-church.py"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jGiaTxH1xCE4"
      },
      "source": [
        "import math"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "P7qFDMHiyL3g"
      },
      "source": [
        "try:\n",
        "    import scipy.stats.norm\n",
        "    norm_logsf = scipy.stats.norm.logsf\n",
        "except ImportError:\n",
        "    def norm_cdf(z):\n",
        "        \"\"\" Cumulative distribution for N(0, 1) \"\"\"\n",
        "        t = 1 / (1 + 0.2316419 * z)\n",
        "        return (1 - 0.3989423 * math.exp(-z * z / 2) *\n",
        "                ((((1.330274429 * t - 1.821255978) * t\n",
        "                    + 1.781477937) * t - 0.356563782) * t + 0.319381530) * t)\n",
        "\n",
        "    def norm_logsf(z):\n",
        "        \"\"\" Logarithm of the survival function for N(0, 1) \"\"\"\n",
        "        try:\n",
        "            return math.log(1 - norm_cdf(z))\n",
        "        except ValueError:\n",
        "            return float('-inf')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rBvVyjjgzhc0"
      },
      "source": [
        "# Alignment costs: -100*log(p(x:y)/p(1:1))\n",
        "bead_costs = {\n",
        "     (1, 1): 0,\n",
        "     (2, 1): 230,\n",
        "     (1, 2): 230,\n",
        "     (0, 1): 450,\n",
        "     (1, 0): 450,\n",
        "     (2, 2): 440\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DS1aZRQEzmUw"
      },
      "source": [
        "# Length cost parameters\n",
        "mean_xy = 1\n",
        "variance_xy = 6.8\n",
        "LOG2 = math.log(2)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_y6qDmOwzoId"
      },
      "source": [
        "def length_cost(sx, sy):\n",
        "    \"\"\" -100*log[p(|N(0, 1)|>delta)] \"\"\"\n",
        "    lx, ly = sum(sx), sum(sy)\n",
        "    m = (lx + ly * mean_xy) / 2\n",
        "    try:\n",
        "        delta = (lx - ly * mean_xy) / math.sqrt(m * variance_xy)\n",
        "    except ZeroDivisionError:\n",
        "        return float('-inf')\n",
        "    return - 100 * (LOG2 + norm_logsf(abs(delta)))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8GqFpu51zp1Y"
      },
      "source": [
        "def _align(x, y):\n",
        "    m = {}\n",
        "    for i in range(len(x) + 1):\n",
        "        for j in range(len(y) + 1):\n",
        "            if i == j == 0:\n",
        "                m[0, 0] = (0, 0, 0)\n",
        "            else:\n",
        "                m[i, j] = min((m[i-di, j-dj][0] +\n",
        "                               length_cost(x[i-di:i], y[j-dj:j]) +\n",
        "                               bead_cost,\n",
        "                               di, dj)\n",
        "                               for (di, dj), bead_cost in bead_costs.items()\n",
        "                               if i-di>=0 and j-dj>=0)\n",
        "\n",
        "    i, j = len(x), len(y)\n",
        "    while True:\n",
        "        (c, di, dj) = m[i, j]\n",
        "        if di == dj == 0:\n",
        "            break\n",
        "        yield (i-di, i), (j-dj, j)\n",
        "        i -= di\n",
        "        j -= dj"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pZHLQTMzzvcO"
      },
      "source": [
        "def char_length(sentence):\n",
        "    \"\"\" Length of a sentence in characters \"\"\"\n",
        "    return sum(1 for c in sentence if c != ' ')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "l4-C9VEjzwzL"
      },
      "source": [
        "def align(sx, sy):\n",
        "    \"\"\" Align two groups of sentences \"\"\"\n",
        "    cx = list(map(char_length, sx))\n",
        "    cy = list(map(char_length, sy))\n",
        "    for (i1, i2), (j1, j2) in reversed(list(_align(cx, cy))):\n",
        "        yield ' '.join(sx[i1:i2]), ' '.join(sy[j1:j2])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bQeaRyNZzyhz"
      },
      "source": [
        "def read_blocks(f):\n",
        "    block = []\n",
        "    for l in f:\n",
        "        if not l.strip():\n",
        "            yield block\n",
        "            block = []\n",
        "        else:\n",
        "            block.append(l.strip())\n",
        "    if block:\n",
        "        yield block"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7XRIeJKFzz7U"
      },
      "source": [
        "def main(corpus_x, corpus_y):\n",
        "    with open(corpus_x) as fx, open(corpus_y) as fy:\n",
        "        for block_x, block_y in zip(read_blocks(fx), read_blocks(fy)):\n",
        "            for (sentence_x, sentence_y) in align(block_x, block_y):\n",
        "                print('%s ||| %s' % (sentence_x, sentence_y))"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}