2d:null 2e:["$","title",null,{"children":"Automatic Layout Detection in Spreadsheets | Leo Orpilla III | Observable"}] 33:[{"id":"003645d0ce16e79f0797823af515ec034ad3f1a513a166520a3f556b5c5452b6ce9bd700d19fb0aa88e19a594d0a8ce1158289a8120886874988bdb73fba0e1d","href":"https://static.observableusercontent.com/files/003645d0ce16e79f0797823af515ec034ad3f1a513a166520a3f556b5c5452b6ce9bd700d19fb0aa88e19a594d0a8ce1158289a8120886874988bdb73fba0e1d","name":"referendum2023@1.xlsx","type":"application/vnd.openxmlformats-officedocument.spreadsheetml.sheet","lastModified":1699278433974.585,"size":7237},{"id":"8b3415a70fd09b3415d598fb6dacfbe4b049b44d42d7b532d3080f1c9eed9df26dfb56921209a2d8253b1f4df1a9c477c1f8e0fc20ffe0657dd24ef3e9c32731","href":"https://static.observableusercontent.com/files/8b3415a70fd09b3415d598fb6dacfbe4b049b44d42d7b532d3080f1c9eed9df26dfb56921209a2d8253b1f4df1a9c477c1f8e0fc20ffe0657dd24ef3e9c32731","name":"referendum2023.xlsx","type":"application/vnd.openxmlformats-officedocument.spreadsheetml.sheet","lastModified":1699271596838.962,"size":7169},{"id":"2556fffff1aa63a908f8f1136b68f0daea96c5d57beb0f8746e01cccda28c5ee88aa345c3afef63c0973cc7f5619bb3abf275c88101e7dc4c12ee168b184cdae","href":"https://static.observableusercontent.com/files/2556fffff1aa63a908f8f1136b68f0daea96c5d57beb0f8746e01cccda28c5ee88aa345c3afef63c0973cc7f5619bb3abf275c88101e7dc4c12ee168b184cdae","name":"referendum2023@2.xlsx","type":"application/vnd.openxmlformats-officedocument.spreadsheetml.sheet","lastModified":1699278574526.283,"size":7233}] 31:{"id":"83b61f3e5e1780ff","slug":"automatic-layout-detection-in-spreadsheets","title":"Automatic Layout Detection in Spreadsheets","thumbnail":"1a131ca925794a9002887f16a1371149ebdcb240535a2f3ea17414412f1dd07f","access_level":"public","create_time":"$D2023-11-06T09:17:46.723Z","update_time":"$D2023-11-09T12:52:51.922Z","view_time":null,"first_public_time":"$D2023-11-06T11:55:13.758Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"304df413ac6d9b3b","login":"ldgrp","name":"Leo Orpilla III","avatar_url":"https://avatars-next.observableusercontent.com/9743f8415274ff1b872aff405e8a77d6dd9c25f412b1ce8853f1dee939c67e9a","tier":"starter_2024"},"version":802,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"4d2ca89f2665bbeb","login":"ldgrp","name":"Leo Orpilla III","avatar_url":"https://avatars-next.observableusercontent.com/9743f8415274ff1b872aff405e8a77d6dd9c25f412b1ce8853f1dee939c67e9a","tier":null}],"members":[{"type":"individual","id":"4d2ca89f2665bbeb","login":"ldgrp","name":"Leo Orpilla III","avatar_url":"https://avatars-next.observableusercontent.com/9743f8415274ff1b872aff405e8a77d6dd9c25f412b1ce8853f1dee939c67e9a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Automatic Layout Detection in Spreadsheets","cells":[{"id":0,"value":"# Automatic Layout Detection in Spreadsheets","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":8,"value":"Given a spreadsheet ${tex`S`} with a set of tables ${tex`T`}, can we identify each table ${tex`t_i`} without additional annotation or semantic information from the user?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":22,"value":"This Observable notebook lets you upload an Excel file (also known as a workbook) and extract the tables from it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":20,"value":"viewof file = Inputs.file({ label: \"Upload an .xlsx file\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"The Excel file may contain multiple worksheets.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":51,"value":"viewof worksheet = Inputs.select(await workbook.worksheets.map((w) => w.name), {\n label: \"Select a worksheet\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"The worksheet is visualised as a bitmap. Each cell is assigned a color according to its data type.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":139,"value":"viewof pixelSize = Inputs.range([3, 20], {\n label: \"Pixel Size\",\n step: 1,\n value: 5\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":181,"value":"rectangle = html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":196,"value":"From here, finding tables can be thought of as a **clustering** problem. Finding connected regions via flood fill by considering 4-connectivity or 8-connectivity is not sufficient when considering sparse tables with many empty cells.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":311,"value":"I'm using DBSCAN _(Density-Based Spatial Clustering of Applications with Noise)_ instead of k-means because the resulting clusters can have varying densities and different shapes. _Insert why a centroid-based clustering algo just feels wrong_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":315,"value":"Below, we set up DBSCAN with ${tex`\\varepsilon = ${epsilon}`} and ${tex`minPts = ${minPoints}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":320,"value":"viewof epsilon = Inputs.range([0, 5], {\n label: \"Epsilon\",\n step: 0.01,\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":338,"value":"viewof minPoints = Inputs.range([0, 10], {\n label: \"Min Points\",\n step: 0.1,\n value: 1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":698,"value":"dbscanner = createDBSCAN(epsilon, minPoints, sparsePointData)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"clusters = dbscanner.getClusters()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":288,"value":"labeledData = {\n const clusters = dbscanner();\n const array = new Array(data.length);\n for (let i = 0; i < data.length; i++) {\n array[i] = new Array(data[0].length);\n }\n sparsePointData.forEach((item, i) => {\n array[item.x][item.y] = clusters[i];\n });\n return array;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"rectangleClustered = html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"There are **${clusters.length}** tables identified in this spreadsheet.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":371,"value":"viewof tableSelection = Inputs.select(\n Array.from({ length: clusters.length }, (_, i) => i + 1),\n { label: \"Select a table\" }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":542,"value":"viewof table1 = Inputs.table(table, {\n columns: Array.from({ length: table[0].length }).map((_, i) => i)\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":532,"value":"You can download an Excel file with each table on its own worksheet below.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":501,"value":"download = {\n const a = document.createElement(\"a\");\n const buffer = await outWorkbook.xlsx.writeBuffer();\n const blob = new Blob([buffer], {\n type: \"application/vnd.openxmlformats-officedocument.spreadsheetml.sheet\"\n });\n const url = URL.createObjectURL(blob);\n return html`\n \n `;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":728,"value":"### Libraries","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":491,"value":"exceljs = require(\"exceljs@4.4.0/dist/exceljs.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"jDBSCAN = require(\"jdbscan@1.0.0/dist/jDBScan.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":730,"value":"### Utility Functions","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":215,"value":"createDBSCAN = (epsilon, minPoints, data) =>\n jDBSCAN().eps(epsilon).minPts(minPoints).distance(\"EUCLIDEAN\").data(data)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":753,"value":"createWorkbook = async (stream) => {\n const workbook = new exceljs.Workbook();\n await workbook.xlsx.load(stream);\n return workbook;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":570,"value":"function readWorksheet(workbook, worksheetName) {\n const worksheet = workbook.getWorksheet(worksheetName);\n const rows = new Array(worksheet.rowCount);\n worksheet.eachRow({ includeEmpty: true }, (row, rowNumber) => {\n rows[rowNumber - 1] = new Array(worksheet.columnCount);\n row.eachCell({ includeEmpty: true }, (cell, colNumber) => {\n let value = cell.value;\n if (typeof value === \"string\") {\n value = cell.value.trim();\n\n if (value === \"\") value = null;\n }\n rows[rowNumber - 1][colNumber - 1] = value;\n });\n });\n return rows;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":713,"value":"matrixArrayToPointData = (array) =>\n array.flatMap((row, rowIndex) =>\n row.map((item, colIndex) => ({ item, x: rowIndex, y: colIndex }))\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"pointDataToMatrixArray = (pointData) => {\n let result = [];\n\n if (pointData.length === 0) return result;\n\n let minX = pointData[0].x;\n let maxX = pointData[0].x;\n let minY = pointData[0].y;\n let maxY = pointData[0].y;\n\n for (const item of pointData) {\n minX = Math.min(minX, item.x);\n maxX = Math.max(maxX, item.x);\n minY = Math.min(minY, item.y);\n maxY = Math.max(maxY, item.y);\n }\n\n const rows = maxX - minX + 1;\n const cols = maxY - minY + 1;\n\n result = new Array(rows);\n for (let i = 0; i < rows; i++) {\n result[i] = new Array(cols);\n }\n\n for (const item of pointData) {\n result[item.x - minX][item.y - minY] = item.item;\n }\n\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"visualizeGrid = (canvas, array, cellSize, borderSize, f) => {\n const ctx = canvas.getContext(\"2d\");\n const numRows = array.length;\n const numCols = array[0].length;\n\n const borderWidth = borderSize * 2;\n canvas.width = numCols * (cellSize + borderWidth);\n canvas.height = numRows * (cellSize + borderWidth);\n\n for (let i = 0; i < numRows; i++) {\n for (let j = 0; j < numCols; j++) {\n const value = array[i][j];\n // Draw the cell with a black border\n ctx.fillStyle = \"black\";\n ctx.fillRect(\n j * (cellSize + borderWidth),\n i * (cellSize + borderWidth),\n cellSize + borderWidth,\n cellSize + borderWidth\n );\n // Now draw the cell\n ctx.fillStyle = f(value, i, j);\n ctx.fillRect(\n j * (cellSize + borderWidth) + borderSize,\n i * (cellSize + borderWidth) + borderSize,\n cellSize,\n cellSize\n );\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":84,"value":"function getDataType(str) {\n if (str === null || String(str).trim().length === 0) {\n return \"empty\";\n }\n if (!Number.isNaN(Number(str))) {\n return \"number\";\n }\n return \"string\";\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"getColorFromDataType = (dataType) => {\n switch (dataType) {\n case \"empty\":\n return \"white\";\n case \"string\":\n return \"red\";\n case \"number\":\n return \"blue\";\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"getColorFromCell = (value, row, col) => {\n getColorFromDataType(getDataType(value));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":745,"value":"### Data","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":748,"value":"referendum = FileAttachment(\"referendum2023@2.xlsx\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"fileBlob = await (file ?? referendum).blob()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":573,"value":"workbook = createWorkbook(fileBlob)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"data = readWorksheet(workbook, worksheet)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":269,"value":"sparsePointData = matrixArrayToPointData(data).filter((x) => x.item != null)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"{\n const canvas = document.getElementById(rectangle.id);\n visualizeGrid(canvas, data, pixelSize, 1, (value, row, col) => getColorFromDataType(getDataType(value)));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"{\n const canvas = document.getElementById(rectangleClustered.id);\n const viridisColors = d3\n .range(clusters.length + 1)\n .map((i) => d3.interpolateViridis(i / clusters.length));\n visualizeGrid(canvas, data, pixelSize, 1, (value, row, col) => {\n const cluster = labeledData[row][col];\n if (cluster != null) {\n if (cluster === 0) {\n return \"gray\";\n }\n if (cluster === tableSelection) {\n return \"red\";\n }\n return viridisColors[cluster];\n }\n\n return \"white\";\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"table = pointDataToMatrixArray(\n clusters[tableSelection - 1].parts.map((i) => sparsePointData[i])\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"outWorkbook = {\n let workbook = new exceljs.Workbook();\n\n for (let i = 0; i < clusters.length; i++) {\n let worksheet = workbook.addWorksheet(`Table ${i + 1}`);\n let table = pointDataToMatrixArray(\n clusters[i].parts.map((item) => sparsePointData[item])\n );\n\n // Add each row of data to the worksheet\n for (let row of table) {\n worksheet.addRow(row);\n }\n }\n return workbook;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 32:"$31:body"